Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [complexity-classes]

Computational complexity classes and their relations

3
votes
1answer
213 views

Dp completeness of a problem

Given a Boolean formula $\varphi$ over the variables $\{x_1...x_n\}$ , an assignment $T_0$ for $\varphi$ and an integer $k$, I am interested in the following question: Does $k$ is the minimal number ...
4
votes
0answers
143 views

On status of Valiant's $NC^2=P^{\#P}$ provability program?

In here it is written 'A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that $NC^2=P^{\#P}\dots$'.... This was a decade back. What is the rationale (at ...
2
votes
1answer
163 views

On $\#P\subseteq FP^{\Sigma_{f(n)}^P}$?

Is it known that permanent of a $0/1$ $n\times n$ matrix $M$ is computable in polynomial or randomized polynomial time with access to a ${\Sigma_{(\log n)^c}^P}$ oracle where $0<c$ holds and $\...
2
votes
1answer
121 views

On $\Delta_i^P$

We know $P\subseteq NP\cap coNP\subseteq\Delta_i^P=P^{\Sigma_{i-1}^P}\subseteq \Sigma_i^P\cap\Pi_i^P=NP^{\Sigma_{i-1}^P}\cap coNP^{\Sigma_{i-1}^P}$. If $P=BPP$ is there a 'higher' randomized class ...
1
vote
0answers
128 views

Co-Partition Problem: Why is this proof for it being in NP wrong? [closed]

So I have this wrong proof that the problem "Co-Partition" is in NP. I know the proof is wrong because I've encountered it in an educational environment and was told that it's not working. I don't, ...
2
votes
0answers
103 views

What is the complexity of computation of zero point by Rieman zeta function?

What is the complexity of computation of zero point by Rieman zeta function? That is, given s, whether ζ(s)=0? Is it in P? Any reference is appreciated.
0
votes
1answer
227 views

${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$

We know that ${\bf NP} \subseteq {\bf PH} \subseteq {\bf PSPACE}$. We also know that ${\bf E} \subset {\bf EXP}$, where ${\bf E} = \cup_c DTIME[2^{cn}]$ and ${\bf EXP} = \cup_c DTIME[2^{n^c}]$. It ...
4
votes
1answer
119 views

Descriptive model theory classification of Counting hierarchy

Descriptive model theory uses logic to characterize complexity classes How to model Counting Hierarchy PSPACE in descriptive model theory?
9
votes
2answers
249 views

Is there a computing problem which is in quasi-polynomial time but is (maybe) not in $\beta P$?

Quasi-polynomial time, or QP for short, is a complexity class on deterministic Turing machine. Here is the precise definition:https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp While βP is a ...
3
votes
1answer
201 views

On $NP$ and $XP$ classes?

On page 33 venn diagram in http://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf it is implied that $XP\subseteq NP$. Below this there is a statement which says $XP\not = NP$ unless $P=NP$. Is ...
16
votes
0answers
268 views

Intermediate problems between PSPACE and EXPTIME

Intermediate problems between P and NP are quite famous, and are sometimes considered as complexity classes by themselves. Do you know of any problem that is known to be PSPACE-hard and in EXPTIME, ...
7
votes
2answers
246 views

Complexity of comparison unary>binary

What is the smallest widely-known complexity class to which $$\left\{\langle i,j\rangle\middle|\begin{array}{@{}l@{\ }l@{}} & i\ \text{is a unary encoding of a positive integer}\ \hat\imath\\\...
-3
votes
1answer
176 views

Is finding a solution harder than verifying a solution? [closed]

Is there any known problem in Comp science where determinisitically finding a "non-trivial" solution to that problem is asymptotically easier than verifying a solution?
1
vote
1answer
196 views

A question of relationships between #P and PSPACE [closed]

Let us assume there is some machine X that converts boolean formula to following form in polynomial time: $$\Phi(x_1, x_2 .. x_m) = r_1(x_{i_1}, x_{j_1}, x_{k_1}) \land r_2(x_{i_2}, x_{j_2}, x_{k_2}) ...
9
votes
1answer
234 views

Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

Background We know that $P^{\#P} \subseteq PSPACE$. In addition, we known from Toda's theorem that $PH \subseteq P^{\#P}$. For more background on $\#P$, see here: https://en.wikipedia....
6
votes
0answers
181 views

Does the existence of an RP-complete language imply P = RP?

(I'm not sure if this is research-level, but I couldn't find an answer to this question elsewhere) The question of whether there exists an RP-complete language seems to be open, but I guess we believe ...
3
votes
1answer
187 views

Looking for approximation class between NPO and Exp-APX

I'm trying to identify the approximation hardness of some maximization problem A. In problem A, finding a solution whose quality is 0 (i.e. such that the value returned by the objetive function is 0) ...
1
vote
1answer
83 views

Running multiple rounds of a BQP computation, without multiple measurements? [closed]

BQP as usually defined is: the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. Just like BPP, the choice of 1/...
7
votes
1answer
316 views

Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

If it is unknown, are there reasons to believe that they might not be equal?
6
votes
1answer
202 views

What's the relationship between ASP-complete and #P-complete?

Given that ASP-reductions by definition are parsimonious and parsimonious reductions preserve #P-completeness, one might think that the counting version of all ASP-complete problems are also #P-...
7
votes
1answer
824 views

k-Vertex Cover problem is in parameterized Log space

$k$-Vertex Cover: Given a graph $G = (V, E)$ where $V$ is a set of vertices and $E$ a set of edges, and an integer $k$, the $k$-Vertex Cover problem determines if there exists a subset of vertices $...
4
votes
0answers
71 views

Non-trivial PCP characterizations of complexity classes beyond ELEMENTARY?

There are interesting results of the form $PCP[a(n), b(n)] = \texttt{SOMECLASS(n)}$ for multiple classes in the exponential hierarchy: the most famous one is probably $PCP[O(log(n)), O(1)] = NP$. Are ...
8
votes
1answer
143 views

Finding a certificate if E=NE

If $\textbf{P}= \textbf{NP}$ then for every language from $\textbf{NP}$ there exists an algorithm of finding a certificate in polynomial time. Assume that $\textbf{E} = \textbf{NE}$. Is it true that ...
4
votes
1answer
148 views

$NotTooManyP^{cc}$ class in communication complexity

Class $P^{cc}$ is class of languages admitting deterministic communication protocol with polylog bits of communication. Class $NP^{cc}$ is class of languages admitting nondeterministic communication ...
8
votes
0answers
116 views

What can we say about AM[log n]?

It is known that $\textbf{AM}[O(1)] = \textbf{AM}$. Since $\textbf{IP}=\textbf{PSPACE}$ we have $\textbf{AM}[poly(n)] = \textbf{PSPACE}$. Can we say something about $\textbf{AM}[ f(n)]$, where $f$ ...
0
votes
0answers
79 views

Permanent in Bounded error Quasi Poly time

Is there any consequence to complexity theory if Permanent has a BQP (classical quasipoly version of BPP)? Is there any consequence to complexity theory if Permanent has a QP (classical quasipoly ...
9
votes
1answer
238 views

Non-uniform version for the whole polynomial hierarchy

The non-uniform versions of P, NP and coNP are P/poly, NP/poly and coNP/poly. Similarly, we can define a non-uniform version for each level in the PH. For example: $\Sigma_2$/poly consists of ...
7
votes
0answers
85 views

Is the class NSC closed under complement?

The class $\mathsf{NSC}$ is defined as $\bigcup_{k\in\mathbb{N}}\mathsf{NSC}^k$, where $\mathsf{NSC}^k = \mathsf{NTIMESPACE}[\mathsf{poly},\mathsf{log}^k]$. In a 1991 paper Mix Barrington and McKenzie ...
2
votes
0answers
62 views

Is there a relationship between the probabilistic interepretation of Sherali-Adams SDP hierarchy and the Lasserre SDP hierarchy?

Firstly note this paper http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf where a Lasserre SDP is being setup for the independent set probblem at the bottom of page 4 where the author says says, ...
0
votes
1answer
128 views

Why are these two definitions of PLS equivalent?

In the definition of the complexity class $\textsf{PLS}$ we have an algorithm for improving the solutions locally. I have come across the following two definition of such an algorithm. there is a ...
9
votes
1answer
384 views

2-NEXPTIME-complete problems

We have a problem and we found an algorithm that appear to be 2-nexptime. I would like to find known 2-nexptime-complete problems in order to find a lower bound. I found in literature mainly two ...
-6
votes
1answer
127 views

Is the difference of two languages in NP-complete an NP-complete too? [closed]

Given two languages $L_{1} \in NP$ and $L_{2} \in \textit{NP-complete}$ such that $L_{1} \cup L_{2} \in \textit{NP-complete}$, Is $L_{1}$ in $\textit{NP-complete}$ too?
5
votes
0answers
192 views

Circuit complexity class of polynomial factoring and Hensel lifting in Zassenhaus' algorithm?

Given a primitive polynomial (gcd of coefficients is $1$) in $\Bbb Z[x]$ we have a polynomial time factoring algorithm for this that runs in time polynomial in degree $d$ and number of bits in ...
6
votes
0answers
173 views

The relation between RP, BPP and NP [duplicate]

I have the following thoughts so I'd like to hear are there any straightforward implications which might support or undermine them. You have a class BPP where problems have a TM with bounded two side ...
1
vote
1answer
180 views

Complexity of permanent modulo prime

Given $M\in\Bbb Z^{n\times n}$ with $O(n)$ bit entries (could be all in $\{0,1\}$), $p$ a prime of $O(n^\alpha)$ bits for some $\alpha\in(0,1]$ and a $c,d\in\Bbb Z$ with $0\leq c<d<p$, is 'Is $\...
5
votes
1answer
327 views

DTIME and PSPACE

Most people believe that $\mathsf{P} \not= \mathsf{PSPACE}$ and $\mathsf{PSPACE} \not=\mathsf{EXP}$. Is there a function $f$ such that $f(n) < 2^n$ and $f(n) > p(n)$ for every polynomial $p$ (...
5
votes
2answers
554 views

XOR-SAT to Horn-SAT reduction

Horn-SAT (conjunction of Horn clauses) is P-complete and XOR-SAT (conjunction of xor clauses) is in P. This means that there is a reduction from XOR-SAT to Horn-SAT weaker than a polynomial reduction. ...
11
votes
1answer
277 views

$\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$

Is $\mathsf{NP^{PP}} = \mathsf{P^{PP}}$? Or, more generally, Is $\mathsf{NP^{PP}} \subseteq \mathsf{P^{PP}/poly}$?
5
votes
0answers
125 views

An oracle in $\mathsf{NEXP}$ that separates ZPP from BPP

Does there exist an oracle $A \in \mathsf{NEXP}$ such that $ \mathsf{ZPP}^A \neq \mathsf{BPP}^A$?
2
votes
1answer
246 views

Complexity involving connected components of 0/1 matrix

Assume a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where each step you take you ...
4
votes
0answers
174 views

Subexponential algorithms vs separations

Williams (see also slide 29 here) has shown that an $\frac{2^{n}}{n^{10}}$ algorithm for satisfiability of circuits belonging to a class $\mathcal{C}$ imply that $\mathrm{NEXP}\nsubseteq \mathcal{C}$. ...
7
votes
1answer
150 views

What are the hardness results known for CSP over $\mathbb{F}_q$?

I found two related papers, There is a UGC hardness result here, https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf A kind of a stronger result might be found in these two other papers, http://...
4
votes
0answers
120 views

Is there a certificate definition for polyL?

Arora explained in his book a certificate definition for $\mathsf{NL}$ using a read-once tape. Can we apply a similar definition for the class $\mathsf{polyL}$?
2
votes
1answer
256 views

Is there any good literature on the computational complexity of function problems?

There are some cstheory questions that touches function-problems. Like this: Complexity class corresponding to sorting So here is the question: Is there good literature about the computational ...
1
vote
0answers
93 views

Two definitions of $QMA$

In this question, I am trying to understand the equivalence between the following two definitions of the complexity class QMA. In Quantum Computational Complexity, John Watrous defines the class QMA ...
5
votes
1answer
394 views

How is the VP=VNP question in char 2 different from other char? What is the current frontier in regards to this question?

What are the caveats one should be aware of when pursuing VP=VNP question in char 2 compared to other char? What is the current frontier in regards to this question?
13
votes
1answer
370 views

Problems in NC not known to lie in NC2

Are there interesting problems that are in $\mathsf{NC}$ but not known to be in $\mathsf{NC^{2}}$? In the paper 'A Taxonomy of Problems With Fast Parallel Algorithms', Cook mentions that MIS was known ...
1
vote
0answers
50 views

About increasing the objective values of certificates for Max-Clique SDP

Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G_1$ of size $n$ and ...
2
votes
0answers
111 views

What would faster Fourier Transform(FFT?) and/or multiplication algorithms imply?

There are many problems which have implications on P vs. NP and other complexity classes. Supposing that we're interested in Fourier transforms and/or multiplication algorithms, do faster Fourier ...
3
votes
0answers
104 views

Are there analogues of Specker sequences for other complexity classes?

Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a_i)_{i \in \mathbb{N}}$ such that (1) the function $i \...