# Questions tagged [complexity-classes]

Computational complexity classes and their relations

674 questions
Filter by
Sorted by
Tagged with
876 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 ...
• 10.6k
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 ...
• 6,842
4k 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 ...
• 16.5k
520 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 ...
• 460
571 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 ...
• 460
465 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 ...
• 16.5k
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 ...
• 16.5k
1k 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 ...
• 13.6k
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? ...
• 1,955
286 views

798 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 ...
• 5,116
752 views

• 37.3k
619 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? (...
• 37.3k
3k 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 "...
• 9,870
2k 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 ...
• 398
825 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 ...
• 8,821