检索结果-内蒙古大学图书馆

On optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography

THEORY OF COMPUTING SYSTEMS 2012年第2期51卷 179-195页

作者： Hirsch, Edward A. Itsykson, Dmitry Monakhov, Ivan Smal, Alexander VA Steklov Math Inst St Petersburg 191011 Russia

The existence of an optimal propositional proof system is a major open question in proof complexity;many people conjecture that such systems do not exist. Krajiek and Pudlak (J. Symbol. Logic 54(3):1063, 1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (Theor. Comput. Sci. 412(4-5):478, 2011) recently presented a conjecture implying that such an algorithm does not exist. We show that if one allows errors, then such optimal algorithms exist. The concept is motivated by the notion of heuristic algorithms. Namely, we allow an algorithm, called a , to claim a small number of false "theorems" and err with bounded probability on other inputs. The amount of false "theorems" is measured according to a polynomial-time samplable distribution on non-tautologies. Our result remains valid for all recursively enumerable languages and can also be viewed as the existence of an optimal weakly automatizable heuristic proof system. The notion of a heuristic acceptor extends the notion of a classical acceptor;in particular, an optimal heuristic acceptor for any distribution simulates every classical acceptor for the same language. We also note that the existence of a --language with a polynomial-time samplable distribution on that has no polynomial-time heuristic acceptors is equivalent to the existence of an infinitely-often one-way function.

关键词： Propositional proof complexity optimal algorithm Infinitely-often one-way

来源：评论

学校读者我要写书评

暂无评论

On an optimal randomized acceptor for graph nonisomorphism

引用

INFORMATION PROCESSING LETTERS 2012年第5期112卷 166-171页

作者： Hirsch, Edward A. Itsykson, Dmitry Russian Acad Sci Steklov Inst Math St Petersburg St Petersburg 191023 Russia

An acceptor for a language L is an algorithm that accepts every input in L and does not stop on every input not in L. An acceptor Opt for a language L is called optimal if for every acceptor A for this language there exists polynomial p(A) such that for every x is an element of L, the running time time(Opt)(x) of Opt on x is bounded by p(A)(time(A)(x) + vertical bar x vertical bar) for every x is an element of L. (Note that the comparison of the running time is done pointwise, i.e., for every word of the language.) The existence of optimal acceptors is an important open question equivalent to the existence of p-optimal proof systems for many important languages (Krajicek and Pudlak, 1989;Sadowski, 1999;Messner, 1999 [9,13,11]). Yet no nontrivial examples of languages in NP boolean OR co-NP having optimal acceptors are known. In this short note we construct a randomized acceptor for graph nonisomorphism that is optimal up to permutations of the vertices of the input graphs, i.e., its running time on a pair of graphs (G(1). G(2)) is at most polynomially larger than the maximum (in fact, even the median) of the running time of any other acceptor taken over all permuted pairs (pi(1) (G(1)). pi(2) (G(2))). One possible motivation is the (pointwise) optimality in the class of acceptors based on graph invariants where the time needed to compute an invariant does not depend much on the representation of the input pair of nonisomorphic graphs. In fact, our acceptor remains optimal even if the running time is compared to the average-case running time over all permuted pairs. We introduce a natural notion of average-case optimality (not depending on the language of graph nonisomorphism) and show that our acceptor remains average-case optimal for any probability distribution on the inputs that respects permutations of vertices. (C) 2011 Elsevier By. All rights reserved.

关键词： Computational complexity optimal algorithm Graph isomorphism

来源：评论

学校读者我要写书评

暂无评论

optimal Self Boundary Recognition with Two-Hop Information for Ad Hoc Networks

Optimal Self Boundary Recognition with Two-Hop Information f...

引用

IEEE Wireless Communications and Networking Conference (WCNC)

作者： Chen, Yen-Hsu Chung, Wei-Ho Ni, Guo-Kai Zhang, Hongke Kuo, Sy-Yen Natl Taiwan Univ Dept Elect Engn Taipei 10764 Taiwan

ISBN: (纸本)9781467304375;9781467304368

The ad hoc network is composed of multiple sensor nodes to serve various applications, such as data collection or environmental monitoring. In many applications, the sensor nodes near the boundary of the deployment region provide biased or low-quality information because they have limited number of neighboring nodes and only partial information is available. Hence, the boundary recognition is an important issue in the ad hoc networks. By the statistical approach in high node density networks, Fekete's pioneer work identified the boundary node by number of neighboring nodes and using a specific threshold. By exploiting the number of nodes in the two-hop region, our proposed algorithm has significant improvement of boundary recognition contrasted with Fekete's algorithm in the low-density network. Given the information topology and the cost function, the analyses provide a framework to obtain the optimal threshold for boundary recognition. Besides, the simulation results reveal the proposed algorithm has greater than 90% detection rate and lower than 10% false alarm rate.

关键词： ad hoc networks boiundary recognition decision optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

Parametric study and optimal algorithm of a simultaneous estimation in two-dimensional inverse heat conduction problem

引用

INVERSE PROBLEMS IN SCIENCE AND ENGINEERING 2008年第4期16卷 461-482页

作者： Abboudi, Said Artioukhine, Eugene UTBM Lab Syst Transports SET Dept GMC F-90010 Belfort France UFC Inst Genie Energet CREST UMR 6174FEMTO ST F-90000 Belfort France

A simultaneous estimation of two boundary conditions in a two-dimensional linear heat conduction problem is proposed by numerical approach. The aim is to estimate the evolution of the distributions of the unknown surface heat fluxes from the transient temperature histories taken with several sensors inside a two-dimensional specimen. The inverse numerical algorithm is based on the iterative regularization method and on the conjugate gradient method. Unknown functions are parametrized in the form of a cubic B-spline. The utilization of an optimal choice of the matrix of the descent parameters is at the origin of this method showing an increase in the convergence rate. The effects of the parameters of the cubic B-spline approximation, the number and the position of the sensors and the magnitude of measurement errors on the inverse solutions are discussed.

关键词： inverse problem simultaneous estimation transient conduction two-dimensional heat conduction optimal algorithm iterative regularization

来源：评论

学校读者我要写书评

暂无评论

Study on Non Energy Saving Status Detection of Groundwater Heat Pump System Using Artificial Neural Network Method

Study on Non Energy Saving Status Detection of Groundwater H...

引用

International Conference on Manufacturing Science and Materials Engineering (ICMSME 2011)

作者： Wang, Zhiwei Peng, Yi Zhang, Zhonghe Cao, Wei Li, Peng Xian Univ Architecture & Technol Sch Environm & Municipal Engn Xian 710055 Peoples R China Silian Inteligence Technol Share Co Ltd Xian 710075 Peoples R China

ISBN: (纸本)9783037852897

Presents two types of characteristic data: basic characteristic parameters and index characteristic parameters for non energy saving status detection (NESSD) of groundwater heat pump (GWHP) system, establishes the relationship database between characteristic data and fault factors of NESSD. For three kinds of improving back propagation (BP) algorithms: Variable Learning Rate (VLR) BP algorithm, Scaled Conjugate Gradient (SCG) BP algorithm, and Levenberg-Marquardt (LM) BP algorithm, these various algorithms' comparative study had been conducted on the GWHP system's NESSD. The optimal algorithm among them is determined and the GWHP system's NESSD as cases studies can be carried out based on the most suitable BP algorithm.

关键词： Artificial neural network optimal algorithm non energy saving status detection relationship database groundwater heat pump

来源：评论

学校读者我要写书评

暂无评论

optimal Channel Assignment algorithm for Wireless Networks

Optimal Channel Assignment Algorithm for Wireless Networks

引用

International Conference on Mechatronics and Intelligent Materials

作者： Zeng, Bin Zhang, Jing Liu, Haiqing Naval Univ Engn Wuhan 430030 Hubei Peoples R China Naval Univ Engn Off Sci Res Wuhan 430030 Hubei Peoples R China

ISBN: (纸本)9783037850695

In wireless cellular network, users will share the time-slots channel and bandwidth with voice users. With the characteristic of dynamic slot allocation, some time slots can be allocated to one single user. How to choose the slot allocation methodology is a significant problem when considering the system revenue and users' satisfaction. A new model based on improvement of Markov Decision Process) is developed that can combines the original maximum system revenue model and the call blocking constraints, and will find out the optimal policy of time slots allocation. The experiment result shows that the new algorithm and model is efficient in the channel assignment area of wireless networks.

关键词： Cellular Network Channel Assignment optimal algorithm Markov Decision Process

来源：评论

学校读者我要写书评

暂无评论

Dynamic Programming for optimal Integration of Plug-in Hybrid Electric Vehicles (PHEVs) in Residential Electric Grid Areas

Dynamic Programming for Optimal Integration of Plug-in Hybri...

引用

Annual Conference on IEEE Industrial Electronics Society

作者： Harun TURKER Ahmad HABLY Seddik BACHA Grenoble Electrical Engineering Lab. Grenoble Image Parole Signal Automatique Lab.

ISBN: (纸本)9781467324199

Plug-in Hybrid Electric Vehicles (PHEVs) will strongly penetrate in the car fleet. Based on databases of the houses Daily Loads Profiles (DLPs) and on a probabilistic algorithm of PHEVs connections in residential electric grid areas, this paper determines the minimal charging current or PHEVs charging power which assures that the batteries reached the desired State of Charge (SOC) at the departure time without any charging restriction during peak hours. A dynamic optimization algorithm programming which defines an optimal constant charging current for the PHEV is developed. If charging occurs at home, the application of the proposed optimal algorithm on 10 000 cases shows statistically that a load power chargers for PHEVs charged in residential electric grid areas equals to 373W (230V×1.62A) ensures that 99.4% of the PHEVs batteries have a SOC equals to 100% for the next use.

关键词： Daily Load Profile Dynamic optimization algorithm Minimal charging current or power optimal algorithm Plug-in Hybrid Electric Vehicle Probabilistic algorithm Residential electric grid areas State of Charge

来源：评论

学校读者我要写书评

暂无评论

An optimal and Practical Approach to Single Constant Multiplication

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2011年第9期30卷 1373-1386页

作者： Thong, Jason Nicolici, Nicola McMaster Univ Dept Elect & Comp Engn Hamilton ON L8S 4K1 Canada

We propose an exact solution to the single constant multiplication (SCM) problem. Existing optimal algorithms are limited to constants of up to 19 bits. Our algorithm requires less than 10 s on average to find a solution for a 32 bit constant. optimality is guaranteed via an exhaustive search. We analyze two common SCM frameworks and the corresponding search strategies that each framework facilitates. Combining the strengths of both frameworks, we obtain highly aggressive pruning. The various strategies used in our algorithm and their underlying intuition are discussed extensively in this paper.

关键词： Common subexpression elimination directed acyclic graphs optimal algorithm single constant multiplication

来源：评论

学校读者我要写书评

暂无评论

optimal semi-online algorithms for scheduling problems with reassignment on two identical machines

引用

INFORMATION PROCESSING LETTERS 2011年第9期111卷 423-428页

作者： Min, Xiao Liu, Jing Wang, Yuqing Jiaxing Univ Coll Math & Informat Engn Jiaxing 314001 Peoples R China

In this paper, we consider semi-online minimum makespan scheduling problem with reassignment on two identical machines. Two versions are discussed. In the first version, one can reassign the last job of one machine that is based on the problem proposed by Tan and Yu (2008) 11 in which case the last job of each machine is allowed to be reassigned. An optimal algorithm which has the same competitive ratio root 2 is presented. In the second version we consider the combination of the next two conditions: the total size of all jobs is known in advance and one can reassign the last job of one machine. For this problem an optimal algorithm with competitive ratio is also given. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Scheduling Reassignment Competitive ratio optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

optimal solutions for the economic lot-sizing problem with multiple suppliers and cost structures

引用

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2011年第1-2期37卷 331-345页

作者： Bai, Qing-Guo Xu, Jian-Teng Qufu Normal Univ Sch Operat Res & Management Sci Rizhao 276826 Shandong Peoples R China Harbin Inst Technol Sch Management Harbin 150001 Heilongjiang Peoples R China

This paper considers a multi-supplier economic lot-sizing problem in which the retailer replenishes his inventory from several suppliers. Each supplier is characterized by one of three types of order cost structures: incremental quantity discount cost structure, multiple set-ups cost structure and all-unit quantity discount cost structure. The problem is challenging due to the mix of different cost structures. For all cases of the problem where each supplier is characterized by one of the first two cost structures, some optimality properties are proposed and optimal algorithms based on dynamic programming are designed. For the case where all suppliers are characterized by all-unit quantity discount cost structures, it is hard to design a polynomial time algorithm by the analyzed optimal properties. However, it is proved that one of its special cases can be solved in polynomial time.

关键词： Economic lot-sizing optimal algorithm Dynamic programming Computational complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：