Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
12
votes
3answers
239 views

Is there a natural restriction of VO logic which captures P or NP?

The paper Lauri Hella and José María Turull-Torres, Computing queries with higher-order logics, TCS 355 197–214, 2006. doi: 10.1016/j.tcs.2006.01.009 proposes logic VO, variable-order logic. This ...
12
votes
1answer
727 views

Communication complexity for deciding associativity

Let $S=${$0,...,n-1$} and $\circ : S \times S \rightarrow S$. I want to compute the communication complexity of deciding whether $\circ$ is associative. The model is the following. $\circ$ is given ...
36
votes
13answers
2k views

Easy decision problem, hard search problem

Deciding whether a Nash equilibrium exists is easy (it always does); however, actually finding one is believed to be difficult (it is PPAD-Complete). What are some other examples of problems where ...
23
votes
1answer
718 views

Is $AC^0$ with bounded fanout weaker than $AC^0$?

In the survey "Small Depth Quantum Circuits" by D. Bera, F. Green and S. Homer (p. 36 of ACM SIGACT News, June 2007 vol. 38, no. 2), I read the following sentence: The classical version of $QAC^0$ (...
10
votes
1answer
834 views

What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?

I would like to know the current state of the phase transition for random k-sat, given n variables and m clauses, what is the best known c=m/n for upper and lower bounds.
36
votes
3answers
2k views

Complexity of exponential function

We know that the exponential function $\exp(x,y) = x^y$ over natural numbers is not computable in polynomial time, because the size of the output is not polynomially bounded in the size of the inputs. ...
7
votes
1answer
382 views

Cobham's Result on Efficient Computations

In the following paper: Alan Cobham (1965), "The intrinsic computational difficulty of functions", Proc. Logic, Methodology, and Philosophy of Science II, North Holland. Cobham defined the class P ...
24
votes
4answers
1k views

Separating Logspace from Polynomial time

It is clear that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). There is a wealth of complexity classes between $L$ and $P$. Examples include $NL$,...
28
votes
6answers
2k views

Alternative proofs of Schwartz–Zippel lemma

I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the wikipedia entry. The second proof was discovered by Dana Moshkovitz. Are there any other ...
21
votes
6answers
1k views

References on Circuit Lower Bounds

Preamble Interactive proof systems and Arthur-Merlin protocols were introduced by Goldwasser, Micali and Rackoff and Babai back in 1985. At first, it was thought that the former is more powerful than ...
8
votes
4answers
424 views

Simple question about decision problems

(I am in the middle of my first theoretical cs course, so I apologize in advance for what is probably a stupid question.) So, we say that some language L is in P, which means that a Turing machine ...
10
votes
1answer
395 views

Is there any sparse language known to be in NPI under the $P \neq NP$ assumption ?

I wonder to know wether there are sparse language (even constructed by delayed diagolanization) in NPI under the assumption that $P \neq NP$.
32
votes
1answer
2k views

Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?

In this question, a 3CNF formula means a CNF formula where each clause involves exactly three distinct variables. For a constant 0<s<1, Gap-3SATs is the following promise problem: Gap-3SATs ...
2
votes
2answers
326 views

Separation of limited nondeterminism classes?

It is interesting to find the best lower bound on the number of nondeterministic bits needed to solve satisfiability problem. Let $\beta_k P$ be the class of problems solvable by a nondeterministic ...
21
votes
6answers
984 views

What is the best way to get a close-to-fair coin toss from identical biased coins?

(Von Neumann gave an algorithm that simulates a fair coin given access to identical biased coins. The algorithm potentially requires an infinite number of coins (although in expectation, finitely many ...
8
votes
2answers
373 views

Relativization with Respect to Non-Recursive Oracles

In the paper Relativizations of the P = ? NP Question, Baker et al. showed that there are relativized worlds in which either P = NP or P ≠ NP holds. All oracles in their settings were recursive sets. ...
2
votes
1answer
280 views

Complexity of advice language?

Let $L$ be a language in P/poly. There is then a deterministic polynomial-time Turing machine $M$ with polynomial-sized advice that decides $L$. Consider the language $A(M)$ of all advice strings ...
10
votes
2answers
281 views

Is there known any complexity class containing online counterparts of optimization problems?

Is there known any complexity class containing online counterparts of optimization problems? If not, then how such class can be defined? We know that many problems have their online version: e.g. ...
27
votes
3answers
1k views

Is there a candidate for a natural problem in $P/poly - P$?

I want to know if non-uniformity helps computing functions in practice. It is easy to show that there are functions in $P/poly - P$, take any uncomputable function $f$ and consider the language {$0^{f(...
15
votes
2answers
651 views

SC^2 algorithms for st-connectivity

Savitch gave a deterministic algorithm to solve st-connectivity using $O({\log}^2{n})$ space, implying $NL \subseteq DSPACE({\log}^2{n})$. Savitch’s algorithm runs in time $2^{O({\log}^2{n})}$. It is ...
1
vote
1answer
220 views

Unary languages in $AC^0$?

Barrington, Immerman, and Straubing state circuit complexity classes contain problems which are not computable at all in the ordinary sense (e.g., any unary language is in $\text{AC}^0$) I'd ...
35
votes
3answers
1k views

NC = P consequences?

The Complexity Zoo points out in the entry on EXP that if L = P then PSPACE = EXP. Since NPSPACE = PSPACE by Savitch, as far as I can tell the underlying padding argument extends to show that $$(\...
25
votes
5answers
2k views

Verifying unique solutions of SAT

Consider the following problem: given a CNF formula and an assignment that satisfies this formula, is there another satisfying assignment for this formula ? What is the complexity of this problem ? (...
8
votes
3answers
979 views

Relationship between SPACE(n) and E

Is it known whether SPACE(n) (the class of languages recognized by deterministic TMs with linear space) is a proper subset of E (the class of languages recognized by deterministic TMs in time 2^O(n))?
10
votes
1answer
231 views

Worlds Relative to Which “Invulnerable Generators” Do Not Exist

Invulnerable generators are defined as follows: Let $R$ be an NP relation, and $M$ be a machine which accepts $L(R)$. Informally, a program is an invulnerable generator if, on input $1^n$, it ...
16
votes
5answers
362 views

Stronger notions of uniformizations?

One gap that I was always aware that I don't really understand is between non uniform and uniform computational complexity where the circuit complexity represents the non uniform version and Turing ...
11
votes
2answers
653 views

Hardness of Vertex Separators

For a given graph $G$, the Separator Problem asks whether a vertex or edge set of small cardinality (or weight) exists whose removal partitions $G$ into two disjoint graphs of approximately equal ...
3
votes
2answers
332 views

Complexity of the Hamiltonian Subcycle problem

The problem is as follows: Given a graph $G$, find a (vertex) disjoint set of cycles $C$ on $G$ such that every vertex is visited by a cycle exactly once. My question is then: what is the ...
9
votes
1answer
227 views

closure properties of IP(2pfa) and AM(2pfa)

IP(2pfa) and AM(2pfa) are the classes of languages recognized with bounded error by private and public coin versions, respectively, of interactive proof systems with verifiers that are probabilistic ...
14
votes
1answer
278 views

Machine characterization of $SAC^i$

$SAC^i$ is the class of decision problems solvable by a family of $O({\log}^i{n})$ depth circuits with unbounded-fanin OR and bounded-fanin AND gates. Negations are only allowed at the input level. It ...
15
votes
2answers
941 views

NP-hard problems on expander graphs?

In a 2006 presentation titled EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT? , Nati Linial posed the following open problem: Which $NP$-hard computational problem on graph remain hard when ...
10
votes
1answer
401 views

What are the complexities of the following SAT subsets ?

Assume $P \neq NP$ Let use the following notation ${}^ia$ for tetration (ie. ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$). |x| is the size of the instance x. Let L be ...
6
votes
1answer
862 views

Oracle relative to which BPP = EXP

An oracle construction relative to which BPP = EXP is usually attributed to Heller (Mathematical System Theory Vol. 17, 1984). Unfortunately I don't have the paper available in my library. Could ...
26
votes
3answers
700 views

Intermediate problems between L and NL

It is well-known that directed st-connectivity is $NL$-complete. Reingold's breakthrough result showed that undirected st-connectivity is in $L$. Planar directed st-connectivity is known to be in $UL \...
5
votes
1answer
340 views

Complexity of finding vectors with optimal projection?

Input: a set $T$ of vectors $v_i=(x_i,y_i,z_i)$. Where $x_i,y_i,z_i$ are integers. Output: a subset of vectors $v_1,v_2,...,v_n$ with vector addition $m=\sum v_i$ such that the projection of $m$ on ...
23
votes
1answer
1k views

What is known about the complexity of finding minimum circuits for SAT?

What is known about the complexity of finding minimal circuits that compute SAT up to length $n$? More formally: what is the complexity of a function which, given $1^{n}$ as input outputs a minimal ...
10
votes
5answers
783 views

Complexity Classes for Cases Other Than “Worst Case”

Do we have complexity classes with respect to, say, average-case complexity? For instance, is there a (named) complexity class for problems which take expected polynomial time to decide? Another ...
15
votes
2answers
914 views

Barriers and Monotone Circuit Complexity

Natural proofs is a barrier towards proving lower bounds on the circuit complexity of boolean functions. They do not directly imply any such barrier in proving lower bounds on the $monotone$ circuit ...
13
votes
2answers
412 views

Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model

In a paper titled "On Deniability in the Common Reference String and Random Oracle Model," Rafael Pass writes: We note that when proving security according to the standard zero-knowledge definition ...
8
votes
2answers
452 views

Understanding QMA

This question comes out of an answer Joe Fitzsimons gave to a different question. Most natural complexity classes have a one-line "intuitive description" that helps characterize core problems in that ...
17
votes
2answers
657 views

Hardness of parameterized CLIQUE?

Let $0\le p\le 1$ and consider the decision problem CLIQUE$_p$ Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges Question: does $G$ contain a clique on at ...
8
votes
1answer
487 views

Algorithms and computational complexity of clique and biclique covers

I've been reading a paper by a mathematical chemist. He proposes some indices to measure the complexity of molecules. From here on in, instead of molecules, think undirected connected graphs: a ...
15
votes
10answers
3k views

Intractability of NP-complete problems as a principle of physics?

I'm always intrigued by the lack of numerical evidence from experimental mathematics for or against the P vs NP question. While the Riemann Hypothesis has some supporting evidence from numerical ...
10
votes
3answers
495 views

Is embedding a solution feasible for SAT?

I am interested in "hard" individual instances of NP-complete problems. Ryan Williams discussed the SAT0 problem at Richard Lipton's blog. SAT0 asks whether a SAT instance has the specific solution ...
15
votes
1answer
505 views

Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?

This is a follow up to this question, and is related to this question of Shiva Kinali. It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use ...
25
votes
4answers
2k views

Proofs, Barriers and P vs NP

It is well known that any proof resolving the P vs NP question must overcome relativization, natural proofs and algebrization barriers. The following diagram partitions the "proof space" into ...
15
votes
3answers
304 views

Are there any classes of functions which require provably different resources to compute versus computing their inverse?

Apologies in advance if this question is too simple. Basically, what I want to know is if there are any functions $f(x)$ with the following properties: Take $f_n(x)$ to be $f(x)$ when the domain and ...
9
votes
5answers
416 views

Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results

Are there any known results showing that existence (or non-existence) of finite graphs with specific computable properties imply certain complexity results (such as P = NP)? Here's one completely ...
23
votes
1answer
835 views

Logspace algorithms on graphs with bounded tree width

Tree width measures how close a graph is to a tree. It is NP-hard to compute tree width. The best known approximation algorithm achieves $O(\sqrt{{\log}n})$ factor. Courcelle's theorem states that ...
2
votes
1answer
252 views

Number of Vertex Covers and Permanent

Is there any relationship between the number of vertex covers of a graph $G$ and the permanent of $G$'s adjacency matrix?