Questions tagged [complexity-classes]
Computational complexity classes and their relations
729 questions
4 votes
0 answers
183 views
Does there exists an oracle $O$ such that $P^O=NP$? [closed]
Does there exist an oracle $O$ such that $P^O=NP$ (where $NP$ $\textbf{doesn't}$ have access to $O$)? I understand there exist oracles, such as ${SAT}$, where $NP \subseteq P^{SAT}$ but are there any ...
- 57
8 votes
0 answers
405 views
Reasons to believe $\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP}$
Much has been said about $\mathsf{P} =^? \mathsf{NP}$. Many polls have been done, and now I think almost every expert believes in $\neq$: https://en.wikipedia.org/wiki/P_versus_NP_problem#Context ...
- 181
6 votes
0 answers
211 views
Does $\mathsf{FP} \subseteq \mathsf{FNP}$ really hold?
The following definitions are from Elaine Rich's Automata, Computability and Complexity. The Class FP: A binary relation $Q$ is in $\mathsf{FP}$ iff there is a deterministic polynomial time algorithm ...
- 161
0 votes
0 answers
77 views
Complexity of Acceptance within an Arithmetical Time Limit
What is the complexity of the following decision problem? Input: a Turing machine $M$, a word $\vec{w}$, and a unary primitive recursive function $f : \mathbb{N} \to \mathbb{N}$. Output: "yes&...
- 109
3 votes
0 answers
65 views
Analogy for "Leaf Languages" for Search Problems
In the literature for work on search problems and classes like $\mathsf{TFNP}, \mathsf{FNP}$ (e.g. here by Papadimitriou), they identified some classes of search problems as syntatic (e.g. $\mathsf{...
- 153
2 votes
1 answer
124 views
$\mathsf{FNP}$-completeness and $\mathsf{TFNP}$
In the paper "On total functions, existence theorems and computational complexity" by Megiddo and Papadimitriou, the introduction of section 1 and its subsection 1.1 defined the complexity ...
- 153
1 vote
1 answer
145 views
Does someone know differents characterizations of advices classes P / log^k ? Can we define P / log with circuits?
For sure, $P / \log(n)^k$ can be canonically defined as "TM working in poly time with advice of size log^k". Thank's to Computational power of neural networks: A characterization in terms of ...
- 11
1 vote
1 answer
127 views
Understanding the proof of $MA \subseteq QCMA$, in particular the "pairing function" in QCMA
My question concerns a subtlety in the definitions of $MA$ and $QCMA$ (a.k.a. $MQA$). Here are the definitions I know: By definition, $L \in MA$ iff there exist polynomials $p, q$ and a uniform and ...
- 133
0 votes
0 answers
339 views
Is this problem in NL?
Let $M$ be a usual logspace Turing machine with work tape alphabet $\{Blank,0,1\}$ and $T=|M|$. Now, I define a different machine, let's call it the $T$-guess logspace machine $M^T$ of $M$. This ...
- 67
0 votes
0 answers
68 views
Is lexicographically first topological order on DAG inputs in non-uniform $TC^0$?
I will mention that I am already pretty sure lexicographically first topological order is $NL$ complete (see here), so I think this question might be somewhat equivalent to $NL \subseteq TC^0$` but I ...
- 9
2 votes
0 answers
120 views
Any PPAD and PPADS analogues of the PPA-complete problem LONELY
The PPA-complete problem LONELY can be phrased as follows: Let $C\colon \{0,1\}^n \rightarrow \{0,1\}^n$ with $C(0^n) = 0^n$. Find an $x\neq 0^n$ such that $C(x) = x$ or $C(C(x)) \neq x$, which ...
2 votes
1 answer
151 views
Explicit transformation from FP to #P
Let $f : \{0,1\}^* \rightarrow \mathbb{Z}$ be a function. Suppose we know $f\in FP$ and that $f(x) \ge 0$ for all $x$. I have seen in many places that this implies $f \in \#P$. That is, there exists a ...
- 123
2 votes
1 answer
375 views
Complexity of counting the number of cycles through a particular edge
It is known that counting cycles in a graph is a hard problem (#P-hard). However, what do we know about the following problem: Given a simple, undirected graph $G$ and an edge $e$ of $G$ as input, ...
-4 votes
1 answer
76 views
Does anyone write a scientific paper citing whether the message conjecture has implications in computational complexity theory?
I am keen on the topological game with very few and very simple rules of Hex (of which Einstein had a gameboard on his desk in Princeton, contemporary computing did not exist in his time). I dream of ...
-4 votes
1 answer
387 views
Equivalent complexity classes theorem?
#P is the counting class of problems. NP is essentially the Satisfiability problem. coNP is essentially Unsatisfiability. Technote: #P has range of 1+2^n values. Search phase: enumerate models, to get ...
- 1