# Questions tagged [complexity-classes]

Computational complexity classes and their relations

596 questions
Filter by
Sorted by
Tagged with
4answers
2k views

### Why do equalities between complexity classes translate upwards and not downwards?

Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the ...
3answers
2k views

### Hardness of approximation - additive error

There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for ...
1answer
490 views

### Why are these two definitions of PPAD equivalent?

The complexity class PPAD is usually defined by stating that End-Of-The-Line is PPAD-complete. End-Of-The-Line is a search problem. The input consists of a directed graph in which each node has in-...
2answers
1k views

### Reducing P vs. NP to SAT

The following question uses ideas from cryptography applied to complexity theory. That said, it is a purely complexity-theoretic question, and no crypto knowledge whatsoever is required to answer it. ...
1answer
1k views

### Is #P contained in PSPACE?

It's obvious that NP $\subseteq$ #P. How about #P $\subseteq$ PSPACE? It strikes me as semi-obvious, since we can check whether an assignment (e.g. for SAT) is a solution in polynomial time (and ...
3answers
2k views

### Consequences of #P = FP

Which would be the consequences of #P = FP? I'm interested in both practical and theoretical consequences. From a practical point of view, I'm particularly interested in consequences on Artificial ...
3answers
895 views

### Limits to Parallel Computing

I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject: http://en.wikipedia.org/wiki/NC_%28complexity%29 The ...
1answer
250 views

### Is the problem of finding the “all-terminal connectivity polynomial” polynomially bounded?

I want to proof whether the problem of finding the "all-terminal connectivity polynomial" of a given graph G(V,E) is checkable in a polynomial time. In order to do so I should first proof that it is ...
1answer
279 views

### What is the size of a function?

I'm not sure whether this question should be asked on mathoverflow.com or here, but as it is in the context of computational complexity, I will ask here. Context Oded Goldreich states in his book ...
3answers
265 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 ...
0answers
688 views

### Is Witten's new method of quantization useful for geometric complexity theory? [closed]

The Kempf-Ness theorem (see e.g. arXiv:0912.1132) - that the algebraic quotient of geometric invariant theory is also a symplectic quotient - suggests (to me) that certain physical constructions used ...
2answers
306 views

### Complexity Classes - separations and inclusions [closed]

What are the basic complexity class seperation and inclusion results that everybody should know? (I mean specifically results that are known, and the proofs can be understood by a non-expert) It ...
3answers
473 views

### Which algorithms can be expressed using a total functional language with data parallel operators?

Imagine a functional programming language whose only data types are numerical scalars and arbitrary nestings of arrays. The language lacks any means of unbounded iteration, so the following are ...
1answer
389 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 ...
1answer
426 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$.
2answers
308 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. ...
1answer
242 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 ...
3answers
1k 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))?
1answer
424 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 ...
1answer
909 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 ...
5answers
901 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 ...
3answers
966 views

### Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
1answer
770 views

### LogDCFL-complete problems

LogCFL is the set of all languages that are logspace reducible to a context-free language. Similarly, LogDCFL is the set of all languages that are logspace reducible to a deterministic context-free ...
1answer
2k views

### Reducing #SAT to #MONOTONE-2SAT

The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its ...
2answers
3k views

### Semantic vs. Syntactic Complexity Classes

In his "Computational Complexity" book, Papadimitriou writes: RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the ...
2answers
421 views

### On the class of the FNP version of the Hamiltonian Cycle problem

This post is linked to: FNP complexity class Many places say that the decision version of Hamiltonian Cycle is NP-Complete, and NP-Complete problems are those whose solution can be verified in ...
3answers
532 views

### FNP complexity class

Where can I find more information about the FNP complexity class? The only place I did find anything on FNP was http://en.wikipedia.org/wiki/FNP_(complexity) However, that isn't sufficient for me to ...
1answer
435 views

### Comparing $\mathbf{NP}$ and $\mathbf{E}$

We know that $\mathbf{NP} = \mathbf{NTIME}(n^{O(1)})$ and $\mathbf{E} = \mathbf{DTIME}(2^{O(n)})$. The complexity zoo states that $\mathbf{E}$ does not equal $\mathbf{NP}$, and cites the following ...
2answers
2k views

### Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?

In the "last paragraph" of the "first page" of the following paper: Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler, "If NP Has Polynomial-Size Circuits, then MA = AM," Theoretical ...
1answer
892 views

### Do all complexity classes have a leaf language characterization?

Leaf languages are a beautiful way to uniformly define many complexity classes. Most complexity classes are usually specified by a model of computation (e.g., deterministic/randomized TM), and a ...
1answer
1k views

### Cutting-sticks puzzle

Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2. Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time? ...
1answer
277 views

3answers
635 views

### What evidence is there that $coRP \neq NP$?

What evidence is there that $coRP \neq NP$? $coRP$ is the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input ...
3answers
588 views

3answers
601 views

### Two Variants of NP

Here are two variations on the definition of NP. They (almost certainly) define distinct complexity classes, but my question is: are there natural examples of problems that fit into these classes? (...
5answers
2k views

### Evidence that PPAD is hard?

There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be "...
2answers
1k views

### Is APX contained in NP?

A problem P is said to be in APX if there exists some constant c > 0 such that a polynomial-time approximation algorithm exists for P with approximation factor 1 + c. APX contains PTAS (seen by ...
1answer
675 views

### Best known joint containments for/by NP and Parity-P?

Parity-P is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero ...
2answers
1k views

### What are the consequences of Parity-L = P?

Parity-L is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero ...

1
8 9 10 11
12