The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [complexity-classes]

Computational complexity classes and their relations

536 questions
Filter by
Sorted by
Tagged with
229 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 ...
385 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?
195 views

175 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 ...
270 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 ...
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 ...
532 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 ...
368 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 ...
220 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 ...
126 views

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, ...
498 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 ...
269 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 ...
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) " ...
510 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 ...
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 ...
366 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 ...
5k 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 ...
131 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, ...
167 views

1k 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 ...
285 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 ...
78 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 ...
566 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. ...
189 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 ...
358 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 only ...
2k views

### Statements that imply $\mathbf{P}\neq \mathbf{NP}$

This is sort of an open-ended question - for which I apologize in advance. Are there examples of statements that (seemingly) don't have anything to do with complexity or Turing machines but the ...
447 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 Karp-...
568 views