Computational complexity classes and their relations

learn more… | top users | synonyms

-4
votes
0answers
148 views

The Mortal Matrix problem: how hard is deciding class membership?

Alice's Claim  There exists a Turing machine (TM) that runs in PTIME (but not necessarily provably so) that infallibly separates mortal matrices from non-mortal matrices (but the separation is ...
17
votes
0answers
262 views
+100

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
70 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
237 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?
2
votes
0answers
141 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. ...
11
votes
2answers
199 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 ...
6
votes
2answers
211 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 ...
14
votes
1answer
277 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 ...
4
votes
1answer
122 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 ...
1
vote
0answers
76 views

Computational tractability

Consider the following optimization problem: $\max_{x\in X}\min_{y\in Y} ||f(x,y)||_2$ $X$ and $Y$ are given $H$-polytopes in the positive orthant of $\mathbb{R}^n$ and $f(x,y)$ is a biconvex ...
6
votes
1answer
250 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
73 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 ...
6
votes
0answers
122 views

Problems in BQP but conjectured to be outside P

Wikipedia listed four problems that are in $BQP$ but conjectured to be outside $P$: Integer factorization; Discrete logarithm; Simulation of quantum systems; Computing the Jones polynomial at certain ...
3
votes
1answer
202 views

#P- vs PP-Completeness

Suppose $A$ is any #P-complete problem. Now, $A$ is modified to obtain a decision problem $A'$ not by asking whether there is a solution but whether at least half of the potential solutions are ...
5
votes
1answer
175 views

Easy decision hard counting Parametrized

It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P. Is there a problem, that exhibits the same behavior in ...
1
vote
0answers
55 views

About the sparsest-cut question

Can someone kindly help clarify as to exactly what is the generally accepted definition of the "sparsest cut" problem for a graph? (Isn't the set which achieves the Cheeger constant for a graph, ...
11
votes
0answers
214 views

Impact of proof of NP=co-NP on RP vs co-RP Question?

It is known that P ⊆ RP ⊆ NP and P ⊆ co-RP ⊆ co-NP. In an oracle world: If NP=co-NP, does RP=co-RP=ZPP follow automatically or does it require additional conditions? If NP=PSPACE, does RP=co-RP=ZPP ...
1
vote
0answers
146 views

What's the Impact if proven NP/co-NP=PSPACE on settling P=NP? The future directions it opens to settle/attack P=NP? Remaining classes left outside?

The primary Impact i know would be that: Polynomial Hierarchy collapses to Level 1. NP=co-NP NP=BPP NP=PSPACE BQP=NP and so on.. What are the attack directions it will open for settling P=NP (in ...
11
votes
2answers
1k views

To which complexity class does this language belong?

I was thinking about which class this language belongs: $L =\{ \langle G,k \rangle \mid G $ is a graph, $k$ is a natural number and $k$ is the chromatic number of $G\}$ I thought of $L$ as (1) " ...
10
votes
1answer
131 views

Can differential equations be classed into their own complexity classes?

Problems have been, as a whole, classified, thanks to Computational Complexity. But, in differential equations, is it possible to classify differential equations depending on their computational ...
28
votes
7answers
3k views

Problems with big open complexity gaps

This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves. To be more ...
5
votes
1answer
176 views

possible bridge between group growth theory and complexity theory?

RJ Lipton conjectures a link between group growth theory and complexity theory. Group growth theory has undergone rapid advance in the last decade and has many surface similarities/ parallels with ...
24
votes
4answers
3k views

If P = NP were true, would quantum computers be useful?

Suppose that P = NP is true. Would there then be any practical application to building a quantum computer such as solving certain problems faster, or would any such improvement be irrelevant based on ...
3
votes
0answers
99 views

Is there a PPAD algorithm for computing primes that sum to even numbers?

Goldbach's conjecture states that every even number greater than 2 can be expressed as the sum of 2 primes. I'm interested in this function problem: Given an even natural number n greater than 2, ...
5
votes
0answers
103 views

Complexity of coloring in weakly perfect graphs?

A graph is weakly perfect if the clique number equals the chromatic number, i.e. $\omega(G)=\chi(G)$. Deciding membership is NP-complete according to the paper. Because of the inequality $\omega(G) ...
1
vote
0answers
119 views

Consequences of the existence of the following algorithm: does it imply any complexity class separation / collapse?

Let $G$ be a $3$-regular graph. Let $O$ be the number of vertex covers of $G$ having odd cardinality, and let $E$ be the number of vertex covers of $G$ having even cardinality. Let $\Delta = O - E$. ...
1
vote
1answer
137 views

Problems with exponential lower computational complexity bound [closed]

I am looking for problems which have an algorithm with asymptotically optimal exponential computational complexity or the problem has a lower bound of exponential computational complexity for ...
2
votes
3answers
164 views

How hard is it to find a “well-distributed” subset of models of a propositional formula?

We consider the propositional language $\mathcal{L}_{\mathit{PS}}$ defined over a finite alphabet $\mathit{PS}$ and the usual logical connectives. An interpretation is an assignment $\mathit{PS} ...
14
votes
3answers
314 views

Can typed lambda calculi express *all* algorithms below a given complexity?

I know that the complexity of most varieties of typed lambda calculi without the Y combinator primitive is bounded, i.e. only functions of bounded complexity can be expressed, with the bound becoming ...
0
votes
1answer
257 views

Randomized Algorithm with random input

As per the Yao's principle, in order to lower bound the cost of Randomized algorithm it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm ...
0
votes
0answers
63 views

Understanding MA protocol as a variant of TM for small space setting

MA protocol is one of the most basic models of interactive proofs. Merlin is a prover sending a witness $w$ for given input string $x$, and Arthur is a verifier who verifies if $w$ is a positive ...
2
votes
0answers
118 views

What is the major difference between PP and RP? [closed]

So according to complexity zoo, the definition of RP is: The class of decision problems solvable by an NP machine such that 1.If the answer is 'yes,' at least 1/2 of computation paths accept. ...
1
vote
0answers
174 views

Determine the complexity class of a language [closed]

Let $L'$ be the language containing all the pairs $(G,v)$ where $G$ is a directed graph and $v$ is a vertex in $G$ such that $G$ contains a cycle (i.e. closed walk) that contains $v$ and the number of ...
10
votes
2answers
284 views

Minimum Tree-width of circuit for MAJORITY

What is the minimum tree-width of a circuit over $\{\wedge,\vee,\neg\}$ for computing MAJ? Here MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ outputs 1 iff at least half of its inputs are $1$. I care ...
14
votes
0answers
229 views

What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?

Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows. Is there a result comparable to the ...
18
votes
1answer
482 views

Is P equal to the intersection of all superpolynomial time classes?

Let us call a function $f(n)$ superpolynomial if $\lim_{n\rightarrow\infty} n^c/f(n)=0$ holds for every $c>0$. It is clear that for any language $L\in {\mathsf P}$ it holds that $L\in {\mathsf ...
7
votes
0answers
507 views

Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

I have part of a proof attempt of $\oplus \mathbf{P} \subseteq \mathbf{NP}$. The proof attempt consists of a Karp reduction from the $\oplus \mathbf{P}$-complete problem $\oplus$3-REGULAR VERTEX COVER ...
4
votes
0answers
220 views

Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?

We can write ${\mathsf {NP}}-{\mathsf P}= {\mathsf {NPC}}\cup {\mathsf {NPI}}$ where ${\mathsf {NPC}}$ is the set of ${\mathsf {NP}}$-complete languages (not in ${\mathsf {P}}$ by this partition), ...
1
vote
1answer
353 views

#P-complete problems are at least as hard as NP-complete problems

I just read J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983) and one of the first ...
12
votes
1answer
216 views

Large classes which contain LOGSPACE for which strict inclusions are unknown

The wikipedia page on PSPACE mentions that the inclusion $NL\subset PH$ is not known to be strict (unfortunately without references). Q1: What about $L\subset PH$ and $L\subset P^{\#P}$ - are these ...
1
vote
0answers
135 views

proving speedup phenomenon does not apply to any open complexity class separations

Aaronson recently wrote a blog refuting the idea that there could be some "glitch" in the formulation of the P vs NP conjecture[1] which reminds me of this following question. the Blum speedup ...
3
votes
0answers
143 views

How powerful are weak complexity classes with powerful oracles?

I am interested in complexity classes of the form $A^{B}$, where $A$ and $B$ are complexity classes such that $A \subsetneq \mathsf{P}$ and $\mathsf{NP} \subsetneq B$ are (believed to be) true. ...
4
votes
4answers
828 views

Factoring as a decision problem

I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision ...
4
votes
1answer
385 views

Example of #P-intermediate problem

The previous question Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P ...
0
votes
1answer
134 views

Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$?

The Toda's theorem is a relationship between two different complexity classes: $ \# \mathsf{P} $ and $PH$. He proved that $ \mathsf{PH}\subseteq \mathsf{P}^{\#\mathsf{P}} $. I wonder the following ...
2
votes
0answers
79 views

Padding Arguments for Probabilistic Classes

Do padding arguments exist for probabilistic classes? For example, would $P=BPP\Rightarrow EXP=BPEXP$? What about for space bounded computation? Would constant space derandomization imply $L=RL$ or ...
10
votes
1answer
425 views

NP-complete problem with polynomially many certificates?

Let's call a language $L \in$ NP sparsely certificated if and only if: There exists a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$ such that for every input $x \in \Sigma^*$ of size $n$, if $x ...
5
votes
3answers
317 views

Problems in $\text{PSPACE} \cap \text{Co-NP-Hard}$

I'm in search for examples of decision problems lying in $\text{PSPACE}\cap \text{coNP-hard}$ which are also not (known to be) in $\text{coNP}\cup \text{NP}\cup \text{NP-hard}\cup ...
6
votes
2answers
158 views

Is there an oracle separating Parity-P from PSPACE?

Is $ (\oplus \mathsf{P})^A \not \supseteq \mathsf {PSPACE}^A$ for some language $A$?
2
votes
0answers
94 views

Maximizing a #P-hard function

Suppose I have a #P-hard function $f(S,x)$ where $x\in T$. Is the problem of $\arg\max_x f(S,x)$ guaranteed to be intractable? If so, I want to see some references on this topic. If not, is there a ...