Relocation problems are hard

We show that General Relocation is NP-Complete. However, specific Relocation subprobiems, such as relocation feasibility or Johnson's scheduling problem are shown to be of almost linear complexity.     

Easy sets and hard certificate schemes

Can easy sets only have easy certificate schemes? In this paper, we study the class of sets that, for all NP certificate schemes (i.e., NP machines), always have easy acceptance certificates (i.e., accepting paths) that can be computed in polynomial time. We also study the class of sets that, for all NP certificate schemes, infinitely often have easy acceptance certificates. In particular, we provide equivalent characterizations of these classes in terms of relative generalized Kolmogorov complexity, showing that they are robust. We also provide structural conditions – regarding immunity and class collapses – that put upper and lower bounds on the sizes of these two classes. Finally, we provide negative results showing that some of our positive claims are optimal with regard to being relativizable. Our negative results are proven using a novel observation: We show that the classical “wide spacing” oracle construction technique yields instant non-bi-immunity results. Furthermore, we establish a result that improves upon Baker, Gill, and Solovay's classical result that holds in some relativized world. Received: 12 January 1996 / 9 January 1997     

Easy intruder deduction problems with homomorphisms

We present complexity results for the verification of security protocols. Since the perfect cryptography assumption is unrealistic for cryptographic primitives with visible algebraic properties, we extend the classical Dolev-Yao model by permitting the intruder to exploit these properties. More precisely, we are interested in theories such as Exclusive or and Abelian groups in combination with the homomorphism axiom. We show that the intruder deduction problem is in PTIME in both cases, improving the EXPTIME complexity results of Lafourcade, Lugiez and Treinen.     

Low-Depth Witnesses are Easy to Find

Kolmogorov Complexity measures the amount of information in a string by the size of the smallest program that generates that string. Antunes, Fortnow, van Melkebeek, and Vinodchandran captured the notion of useful information by computational depth, the difference between the polynomial-time-bounded Kolmogorov complexity and traditional Kolmogorov complexity. We show unconditionally how to probabilistically find satisfying assignments for formulas that have at least one assignment of logarithmic depth. The converse holds under a standard hardness assumption though fails if BPP = FewP = EXP. We also prove that assuming the existence of good pseudorandom generators one cannot increase the depth of a string efficiently.     

Easy impossibility proofs for distributed consensus problems

Easy proofs are given, of the impossibility of solving several consensus problems (Byzantine agreement, weak agreement, Byzantine firing squad, approximate agreement and clock synchronization) in certain communication graphs.It is shown that, in the presence ofm faults, no solution to these problems exists for communication graphs with fewer than 3m+1 nodes or less than 2m+1 connectivity. While some of these results had previously been proved, the new proofs are much simpler, provide considerably more insight, apply to more general models of computation, and (particularly in the case of clock synchronization) significantly strengthen the results.Michael J. Fischer is currently Professor of Computer Science at Yale University, New Haven, CT, where he heads the Theory of Computation Group. He is also Editor-in-Chief of the Journal of the Association for Computing Machinery. His research interests include theory of distributed systems, cryptographic protocols, and computational complexity.Dr. Fischer received the B. S. degree in matheamtics from the University of Michigan, Ann Arbor, in 1963, and the M. A. and Ph. D. degrees in applied mathematics from Harvard University, Cambridge, MA, in 1965 and 1968, respectively. He has taught previously at Carnegie-Mellon University, the Massachusetts Institute of Technology, and University of Washington.Nancy Lynch is currently Associate professor of Computer Science at M.I.T., and heads the Theory of Distributed Systems group in M.I.T.'s Laboratory for Computer Science. Her interests are in all aspects of distributed computing theory, including formal models, algorithms, analysis, and correctness proofs. Dr. Lynch received the B.S. degree in mathematics from Brooklyn College in 1968 and the Ph. D. degree in mathematics from M.I.T. in 1972. She has served on the faculty of Tufts University, the University of Southern California, Florida International University, Georgia Tech.Michael Merritt is currently a member of the technical staff with AT&T Bell Laboratories. During the 1984 –85 academic year, he was a visiting lecturer at M.I.T., sponsered by Bell Labs. His research interests include distributed computation, cryptography and security. Dr. Merritt received the B. S. degree in computer science and philosophy from Yale in 1978 and the M. Sc. and Ph. D. degrees in 1980 and 1983, respectively, both in information and computer science from Georgia Tech. He is a member of SIGACT and of Computer Professionals for Social Responsibility.This paper has appeared in the ACM Conference Proceedings of PODC 1985. © 1985, Association for Computing Machinery, reprinted by permission     

Random constraint satisfaction: Easy generation of hard (satisfiable) instances

In this paper, we show that the models of random CSP instances proposed by Xu and Li [K. Xu, W. Li, Exact phase transitions in random constraint satisfaction problems, Journal of Artificial Intelligence Research 12 (2000) 93–103; K. Xu, W. Li, Many hard examples in exact phase transitions with application to generating hard satisfiable instances, Technical report, CoRR Report cs.CC/0302001, Revised version in Theoretical Computer Science 355 (2006) 291–302] are of theoretical and practical interest. Indeed, these models, called RB and RD, present several nice features. First, it is quite easy to generate random instances of any arity since no particular structure has to be integrated, or property enforced, in such instances. Then, the existence of an asymptotic phase transition can be guaranteed while applying a limited restriction on domain size and on constraint tightness. In that case, a threshold point can be precisely located and all instances have the guarantee to be hard at the threshold, i.e., to have an exponential tree-resolution complexity. Next, a formal analysis shows that it is possible to generate forced satisfiable instances whose hardness is similar to unforced satisfiable ones. This analysis is supported by some representative results taken from an intensive experimentation that we have carried out, using complete and incomplete search methods.     

Power indices and easier hard problems

The concepts of power_index, satisfiability hypothesis (SH), and structure tree are introduced and used to make sharper hypotheses about a problem's complexity than the problem isNP-complete. These concepts are used to characterize the complexities of a number of basicNP-complete problems, including both CLIQUE and PARTITION which are shown to have power-indices at most 1/2. Also, the problem 3SAT is shown to be solvable deterministically in time exponential only in thesquare root ofv+c, wherev is the number of variables andc is the number of crossovers needed to layout the formula in the plane.The research of R. E. Stearns was supported by NSF Grants DCR 83-03932 and CCR 89-03319, and that of H. B. Hunt was supported by NSF Grants DCR 86-03184 and CCR 89-03319.     

On solving hard problems by polynomial-size circuits

This paper introduces the notions of immunity, complexity core, and Church-randomness for the nonuniform complexity class of languages accepted by polynomial-size circuit families, usually denoted as P/Poly. While it is not known whether Dtime(2^poly) is contained in P/Poly, we show that there exist languages in Exspace that have the property of being immune, or having dense complexity core, or being Church-random with respect to the class P/Poly. Proofs of these results are based on techniques in generalized Kolmogorov complexity theory.     

Random low-degree polynomials are hard to approximate

We study the problem of how well a typical multivariate polynomial can be approximated by lower-degree polynomials over \mathbb F{\mathbb F} . We prove that almost all degree d polynomials have only an exponentially small correlation with all polynomials of degree at most d − 1, for all degrees d up to Θ(n). That is, a random degree d polynomial does not admit a good approximation of lower degree. In order to prove this, we prove far tail estimates on the distribution of the bias of a random low-degree polynomial. Recently, several results regarding the weight distribution of Reed–Muller codes were obtained. Our results can be interpreted as a new large deviation bound on the weight distribution of Reed–Muller codes.     

Monocultures are hard to find in practice

The statement that computer networks executing essentially the same software (for example, a software's various versions and configurations; such as Linux or Windows) present a higher risk of cascading failures than more diversified networks when a serious vulnerability is discovered in that common software has two inherent problems. The first problem is with the concept of "essentially the same software", and the second is with the meaning of "cascading failures".     

Some polynomials that are hard to compute

Using the result of Heintz and Sieveking [1], we show that the polynomials $\text{Σ}{}_{\mathrm{1?j?d}}\text{b}{}^{\mathrm{<mtext>1</mtext><mtext>i</mtext>}}\text{X}{}^{\mathrm{j}}$ with b positive real different from one, and Σ_1?j?dj^rX^j with r rational not integer, are hard to compute.     

Alternatives to truthfulness are hard to recognize

The central question in mechanism design is how to implement a given social choice function. One of the most studied concepts is that of truthful implementations in which truth-telling is always the best response of the players. The Revelation Principle says that one can focus on truthful implementations without loss of generality (if there is no truthful implementation then there is no implementation at all). Green and Laffont (Rev Econ Stud 53:447–456, 1986) showed that, in the scenario in which players’ responses can be partially verified, the revelation principle holds only in some particular cases. When the Revelation Principle does not hold, non-truthful implementations become interesting since they might be the only way to implement a social choice function of interest. In this work we show that, although non-truthful implementations may exist, they are hard to find. Namely, it is NP-complete to decide if a given social choice function can be implemented in a non-truthful manner, or even if it can be implemented at all. This is in contrast to the fact that truthful implementability can be efficiently recognized, even when partial verification of the agents is allowed. Our results also show that there is no “simple” characterization of those social choice functions for which it is worth looking for non-truthful implementations.     

Nested semantics over finite trees are equationally hard

This paper studies nested simulation and nested trace semantics over the language BCCSP, a basic formalism to express finite process behaviour. It is shown that none of these semantics affords finite (in)equational axiomatizations over BCCSP. In particular, for each of the nested semantics studied in this paper, the collection of sound, closed (in)equations over a singleton action set is not finitely based.     

Hard constraint satisfaction problems have hard gaps at location 1

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many well-known problems (such as Maxk-SAT and Max Cut) and is consequently NP-hard. Thus, it is natural to study how restrictions on the allowed constraint types (or constraint language) affect the complexity and approximability of Max CSP. The PCP theorem is equivalent to the existence of a constraint language for which Max CSP has a hard gap at location 1; i.e. it is NP-hard to distinguish between satisfiable instances and instances where at most some constant fraction of the constraints are satisfiable. All constraint languages, for which the CSP problem (i.e., the problem of deciding whether all constraints can be satisfied) is currently known to be NP-hard, have a certain algebraic property. We prove that any constraint language with this algebraic property makes Max CSP have a hard gap at location 1 which, in particular, implies that such problems cannot have a PTAS unless P=NP. We then apply this result to Max CSP restricted to a single constraint type; this class of problems contains, for instance, Max Cut and Max DiCut. Assuming P≠NP, we show that such problems do not admit PTAS except in some trivial cases. Our results hold even if the number of occurrences of each variable is bounded by a constant. Finally, we give some applications of our results.     

Real-time solving of computationally hard problems using optimal algorithm portfolios

Annals of Mathematics and Artificial Intelligence - Various hard real-time systems have a desired requirement which is impossible to fulfill: to solve a computationally hard optimization problem...     

Weakly complete problems are not rare

Certain natural decision problems are known to be intractable because they are complete for E, the class of all problems decidable in exponential time. Lutz recently conjectured that many other seemingly intractable problems are not complete for E, but are intractable nonetheless because they areweakly complete for E (i.e., they are in E and hard for more than a measure 0 subset of E). The main result of this paper shows that Lutz's intuition is at least partially correct: many more problems are weakly complete for E than are complete for E.The main result of this paper states that weakly complete problems arenot rare in the sense that they form a non-measure 0 subset of E. This extends a recent result of Lutz that establishes the existence of problems that are weakly complete, but not complete, for E. The proof of Lutz's original result employs a sophisticatedmartingale diagonalization argument. Here, we simplify and extend Lutz's argument to prove the main result. This simplified martingale diagonalization argument may be applicable to other questions involving individual weakly complete problems.     

Some computational problems in linear algebra as hard as matrix multiplication

We define the complexity of a computational problem given by a relation using the model of computation trees together with the Ostrowski complexity measure. Natural examples from linear algebra are:

KER _n : Compute a basis of the kernel for a givenn×n-matrix,

OGB _n : Find an invertible matrix that transforms a given symmetricn×n-matrix (quadratic form) into diagonal form,

SPR _n : Find a sparse representation of a givenn×n-matrix.

     

Effect of silhouette quality on hard problems in Gait recognition.

Gait as a behavioral biometric has been the subject of recent investigations. However, understanding the limits of gait-based recognition and the quantitative study of the factors effecting gait have been confounded by errors in the extracted silhouettes, upon which most recognition algorithms are based. To enable us to study this effect on a large population of subjects, we present a novel model based silhouette reconstruction strategy, based on a population based hidden Markov model (HMM), coupled with an eigen-stance model, to correct for common errors in silhouette detection arising from shadows and background subtraction. The model is trained and benchmarked using manually specified silhouettes for 71 subjects from the recently formulated HumanID Gait Challenge database. Unlike other essentially pixel-level silhouette cleaning methods, this method can remove shadows, especially between feet for the legs-apart stance, and remove parts due to any objects being carried, such as briefcase or a walking cane. After quantitatively establishing the improved quality of the silhouette over simple background subtraction, we show on the 122 subjects HumanID Gait Challenge Dataset and using two gait recognition algorithms that the observed poor performance of gait recognition for hard problems involving matching across factors such as surface, time, and shoe are not due to poor silhouette quality, beyond what is available from statistical background subtraction based methods.     

三星超值显示器推荐 玩的要简单

产品功能的过多堆砌,对于一些用户来说,不仅仅是成本负担,同时在日常应用中也会有些干扰,大多数用户想要的使用体验并不多,是要简单、不要复杂。