Stack Exchange Network

Stack Exchange network consists of 174 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

7
votes
1answer
289 views

Parity P and AM

What is known about non-trivial inclusions of $\oplus\mathsf{P}$ in other classes? In particular, is it known whether $\oplus\mathsf{P}$ is contained in $\mathsf{AM}$? The same questions apply to the ...
3
votes
0answers
157 views

About lower bounding the sample complexity of a distribution

Given a joint probability distribution over a finite number of random variables (each with a finite range space) of which only a certain subset is observable, is there a notion of "sample complexity" ...
2
votes
0answers
127 views

Complexity of counterexample function and bounded arithmetic

Let $\{L^c_i\}_{i}$ be an efficient enumeration of languages in $DTime(2^{n^c})$, e.g. clocked TMs. Assume $EXP\not = NEXP$. Let $L$ be an $NEXP$-complete language and therefore not in $EXP$. There ...
7
votes
1answer
432 views

Is “two or zero” matching in a bipartite graph NP complete?

I have this problem, which I haven't seen before in the literature: given a bipartite graph and a natural number $k$, can we select at least $k$ of the edges such that each left-hand vertex is ...
1
vote
0answers
137 views

Quantum computer versus Random 3-SAT?

It seems to be commonly believed that quantum computer cannot efficiently solve NP-hard problems. What about the challenging problems in average-case, such as Planted Clique and Random 3-SAT?
2
votes
0answers
174 views

Linear Time Hierarchy and Circuit complexity

By Karp-Lipton Theorem we have: $$PH\subseteq P/poly\Rightarrow PH=\Sigma^p_2$$ So this theorem suggest it is unlikely that $PH\subseteq P/poly$. I want to know is there any similar conditional or ...
19
votes
1answer
606 views

Division by two of functions in #P

Let $F$ be an integer valued function such that $2F$ is in $\#P$. Does it follow that $F$ is in $\#P$? Are there reasons to believe this is unlikely to always hold? Any references I should know ...
3
votes
1answer
223 views

Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?

I'm wondering which is the approximation class of Minimum 0-1 Integer Programming if only non-negative integers are used. That is: minimize $c^T \cdot x$, with $x\in \{0,1\}^n$ and $c\in (\mathbb{Z}^...
2
votes
1answer
375 views

Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?

May be this is trivial but I do not know the answer. As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ holds. As far as we know $$\mathsf{NP}\cup\mathsf{coNP}\subseteq\...
5
votes
2answers
184 views

Popular average-case complexity assumptions

Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?
7
votes
1answer
569 views

Intersection of languages in NP

Can intersection of two languages in NP which are not NP complete be NP complete? Can intersection of two languages in coNP which are not coNP complete be coNP complete? Can intersection of two ...
3
votes
2answers
293 views

Consequences of $NP\subseteq P/poly$ to $BQP$

A post here Consequences of $BQP \subseteq P/poly$? queried on Consequences of $BQP \subseteq P/poly$. It is not known if $NP\subseteq BQP$. In general, what are the consequences of $NP\subseteq P/...
8
votes
2answers
251 views

Uncertainties in GCT program

In https://en.wikipedia.org/wiki/Geometric_complexity_theory it is mentioned that ".. Ketan Mulmuley believes the program, if viable, is likely to take about 100 years before it can settle the P vs. ...
6
votes
3answers
416 views

Natural NP-complete problems with high density?

(This question is related to a previous one, see the discussion in "Almost easy" NP-complete problems, but it may also be of independent interest, so I post it as a separate question.) Let ...
10
votes
1answer
477 views

Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic

Berman–Hartmanis conjecture: all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms[1]. I am interested in a more fine-grained ...
1
vote
1answer
243 views

Is this problem #P-hard and why?

Problem: In a directed graph $G=(V,E)$, each edge $e\in E$ is associated with a weight $w_e$ which is geometrically distributed with a parameter $p$, i.e. $P(w_e=i)=p(1-p)^{i-1}, i\geq 1$. $s,t$ are ...
3
votes
0answers
166 views

Big picture in counting complexities

(1) Is there a relation ( conjectured relation) between $\mathsf{\#P}$ and $\mathsf{CH}$? (2) How does $\tau$ conjecture in complexity of factorial fit in the picture? Is there a good reference? $\...
20
votes
1answer
674 views

“Almost easy” NP-complete problems

Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs. In other words, there is an $A\in$ P, such that $L\Delta A$...
15
votes
4answers
1k views

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

László Babai recently proved that the Graph Isomorphism problem is in quasipolynomial time. See also talk at University of Illinois, Chicago, note from the talks by Jeremy Kun GLL post 1, GLL post 2,...
8
votes
1answer
316 views

Are there more polynomial time problems with complexity lower bounds?

I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below. Exponential Lower Bounds: Claim: If ...
16
votes
2answers
444 views

Potentially equal complexity classes without known contradictory relativizations

What are some examples of pairs of complexity classes $A$ and $B$ such that we do not know whether $A=B$, and we do not know contradictory relativizations either (i.e., we do not know oracles $P$ and ...
7
votes
1answer
242 views

Two DFA intersection emptiness connections to SETH & L vs P

(re "fine grained complexity") Wehar has proved that Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false. does anyone see any particular key proof difficulty, challenge, ...
0
votes
0answers
112 views

Complexity classes for problems that can be solved only from the length of the input

A tally language is a language on an alphabet with only one symbol. One can define complexity classes for tally languages, such as $P_1$ (the tally languages that can be decided in polynomial time). ...
1
vote
0answers
212 views

Is $\mathsf{NP}$ in $\mathsf{NNC}^1$?

Theorem 2.2 in "Nondeterministic circuits, space complexity and quasigroups", by Wolf, 1994 (a technical report version is available here without fee), proves that NP = NNC, where NNC is the class of ...
2
votes
0answers
90 views

Advances in complexity by studying particular problems

When we are trying to figure out in which complexity class a problem lies, we usually try simultaneously to come up with the best algorithm for it, together with the best hardness reduction, until (...
7
votes
0answers
278 views

Why is it so difficult to study Sum of Squares (SoS) algorithms with degree $d>4$?

In many publications on the computational complexity of Sum of Squares (SoS) algorithms, it is typical to study the degree-$4$ relaxation; e.g. Rounding Sum-of-Squares Relaxations Sum-of-Squares ...
8
votes
1answer
240 views

What's the complexity of counting odd nodes in graph?

According to Handshaking Lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are ...
6
votes
0answers
131 views

Does it matter who begins communication in $IP(f(x))$?

Consider $IP(f(x))$, in other words, the class of languages that admit a private coin protocol $(P, V)$ running in $f(x)$ rounds (often in terms of the size of $x$), satisfying standard constraints. ...
3
votes
0answers
102 views

Number theoretic problems complete for $\mathsf{RL}$

Are there number theoretic problems (such as those related to $\mathsf{gcd}$) that are in $\mathsf{RL}$? Can these also be $\mathsf{RL}$-complete problems (is there any $\mathsf{RL}$-complete ...
23
votes
3answers
836 views

What are the relationships between those hypotheses in Fine-Grained Complexity Theory?

Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" ...
3
votes
0answers
59 views

Does simulating chiral gauge theories lie within BQP?

In theoretical physics, there is a branch of quantum field theory dealing with chiral gauge theories. It has been conjectured by Feynman [1] and others that all quantum field theories can be simulated ...
16
votes
1answer
394 views

Complexity classes for proofs of knowledge

Prompted by a question Greg Kuperberg asked me, I'm wondering if there are any papers that define and study complexity classes of languages admitting various kinds of proofs of knowledge. Classes ...
3
votes
1answer
267 views

Is counting the words in a finite regular language #P-complete?

Almost the exact same question was asked here, but nobody proved or cited its #P-completeness! I found this question because I proved it is #P-complete (proof below), and the proof was trivial, but I ...
-2
votes
1answer
131 views

A curious statement in an old blog

In http://blog.computationalcomplexity.org/2009/08/finding-primes.html, a statement is added which reads "Oddly enough we would usually prefer a probabilistic over the deterministic method to find ...
-2
votes
1answer
224 views

Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?

$\mathsf{P/Poly}$ captures those problems that could be solved in polynomial time given some precomputed polynomial number of constants. Is there an analogous complexity class in randomized world ...
12
votes
1answer
383 views

Which complexity class does this number theory problem belong to?

'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by=c$' is $\mathsf{NP}$-complete. Which complexity class does 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by^2=c$' belong to?
8
votes
1answer
195 views

What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?

In [1] it is stated that "It remains an open question as to whether every function in $\#P$ has $TC^0$ circuits (although it is at least known that not all $\#P$ functions have DLogTime-uniform $...
1
vote
0answers
55 views

Analogues of different complexity classes in various models

We suspect following relation: $$TC^0\subsetneq NC^1\subsetneq L\subsetneq NL\subsetneq AC^1\subsetneq NC^2\subsetneq P\subsetneq NP\subsetneq PH\subsetneq PSPACE$$ in Turing/boolean circuit ...
1
vote
1answer
244 views

How does one determine if a mixed bipartite quantum state is entangled or not?

My question is based on the structure of the NP-hardness proof in section 6 (page 17) of this paper, http://arxiv.org/pdf/quant-ph/0303055v1.pdf Mathematically one can think of being given a positive ...
8
votes
1answer
207 views

What is the smallest class of reductions under which there is a $\mathsf{P}$-complete problem?

It is common to define $P$-completeness with respect to log-space many-one reductions. I am looking for a complexity class $C \subseteq \mathsf{L}$ such that there are $\mathsf{P}$-complete problems ...
20
votes
0answers
479 views

What is the power of general poly-size permutation branching programs?

Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions ...
3
votes
0answers
81 views

Are there works on function complexity classes not included in FNP? [closed]

Is there a sort of polynomial hierarchy in the case of function problems?
3
votes
2answers
261 views

What happens to complexity classes if all $\#P$ problems have polynomial-time algorithms?

As title says what happens to other complexity classes if all $\#P$ (Sharp-P) problems have polynomial-time algorithms? What happens to PSPACE?
5
votes
0answers
310 views

PSPACE completeness, with different kinds of reductions

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. ...
13
votes
2answers
368 views

What is an equivalent definition of mP/poly in terms of a Turing machine?

P/poly is the class of decision problems solvable by a family of polynomial-size Boolean circuits. It can alternatively be defined as a polynomial-time Turing machine that receives an advice string ...
11
votes
7answers
606 views

Sufficient conditions for the collapse of Polynomial Hierarchy (PH)

What are some (not well-known) assertions that if true, the PH must collapse? Replies containing a short high-level assertion with reference(s) are appreciated. I tried to reverse-search without much ...
13
votes
1answer
365 views

$\mathsf{EXP}$ vs $\oplus\mathsf{EXP}$

In our recent work, we resolve a computational problem which arose in combinatorial context, under assumption that $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$, where $\mathsf{\oplus{}EXP}$ is the $\mathsf{...
4
votes
1answer
170 views

Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard?

The usage of an $\mathrm{NP}$-oracles which delivers a witness has been proposed for example in [Buss1995]. I would like to see an example of an $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard problem. Can ...
6
votes
1answer
269 views

Complexity of max problem

Consider the problem $\max_x \;||x||_2\\ x\in P\subseteq \mathbb{R}_{\geq 0}^n$ where $||\cdot||$ is Euclidean 2-norm and $P$ is a polytope in positive orthant of $\mathbb{R}^n$. Is this problem ...
0
votes
0answers
91 views

Is this some variant of the Knapsack Problem?

We are a set of items $I = \{I_1, I_2,.. I_n\}$, which need to be placed in a certain number of knapsacks $K$. We can use as many knapsacks as we want and each knapsack has an infinite capacity but ...