We survey the research performed in the last few years on a specific topic: the power of real machines over binary inputs. This research attempts to characterize the classes of decision problems over a finite alphabet...
详细信息
We survey the research performed in the last few years on a specific topic: the power of real machines over binary inputs. This research attempts to characterize the classes of decision problems over a finite alphabet - say {0, 1} - which can be decided by real machines working under several resource restrictions. Non-uniformity appears here in a natural way. However, since this is a technical concept which is not widely known, we summarize in Section 2 some of the intuitive notions, as well as a few basic theorems related to it. In Section 3 we do this for the subject of real machines and then, in Section 4 we present the state of the art of the surveyed topic. We devote Section 1 to introduce the main concepts of complexity theory. Proofs in this article are quite sketchy and are included more to convey intuitive ideas than to completely prove the claimed statements. Bibliographical references to the original literature are supplied for the latter purpose.
Two sets of investigators have recently discovered polynomialtime probabilistic algorithms with small error probability for a problem in NP conjoined with co-NP. The discovery raises the question whether probabilist...
详细信息
Two sets of investigators have recently discovered polynomialtime probabilistic algorithms with small error probability for a problem in NP conjoined with co-NP. The discovery raises the question whether probabilistic algorithms perhaps are more powerful than nondeterministic ones. More specifically, a question arises about the possibilities for discovering a polynomialtime probabilistic algorithm with small error probability for some NP-hard problem. Through an analysis that draws from the work that led to the recent discovery, it is concluded that all NP-hard optimization problems have some probabilistic algorithms with small error bounds.
We initiate the study of the computational complexity of the covering radius problem for lattices, and approximation versions of the problem for both lattices and linear codes. We also investigate the computational co...
详细信息
We initiate the study of the computational complexity of the covering radius problem for lattices, and approximation versions of the problem for both lattices and linear codes. We also investigate the computational complexity of the shortest linearly independent vectors problem, and its relation to the covering radius problem for lattices. For the covering radius on n-dimensional lattices, we show that the problem can be approximated within any constant factor gamma( n) > 1 in random exponential time 2(O(n)). We also prove that suitably defined gap versions of the problem lie in AM for gamma(n) = 2, in coAM for gamma(n) = root n/log n, and in NP boolean AND coNP for gamma(n) = root n. For the covering radius on n-dimensional linear codes, we show that the problem can be solved in deterministic polynomialtime for approximation factor gamma(n) = log n, but cannot be solved in polynomialtime for some gamma(n) = Omega(log log n) unless NP can be simulated in deterministic nO( log log log n) time. Moreover, we prove that the problem is NP-hard for any constant approximation factor, it is Pi(2)-hard for some constant approximation factor, and that it is unlikely to be Pi(2)-hard for approximation factors larger than 2 ( by giving an AM protocol for the appropriate gap problem). This is a natural hardness of approximation result in the polynomialhierarchy. For the shortest independent vectors problem, we give a coAM protocol achieving approximation factor gamma(n) = root n/log n, solving an open problem of Blomer and Seifert (STOC' 99), and prove that the problem is also in coNP for gamma(n) = root n. Both results are obtained by giving a gap-preserving nondeterministic polynomialtime reduction to the closest vector problem.
The polynomialhierarchy plays a central role in classical complexity theory Here, we define a quantum generalization of the polynomialhierarchy, and initiate its study. We show that not only are there natural comple...
详细信息
The polynomialhierarchy plays a central role in classical complexity theory Here, we define a quantum generalization of the polynomialhierarchy, and initiate its study. We show that not only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Using the same techniques, we also obtain hardness of approximation for the class QCMA. Our approach is based on the use of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomialhierarchy [Umans, FOCS 1999]. The problems for which we prove hardness of approximation for include, among others, a quantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian problem with hybrid classical-quantum ground states.
暂无评论