# Questions tagged [complexity-classes]

Computational complexity classes and their relations

596 questions
Filter by
Sorted by
Tagged with
1answer
46 views

### KRW Conjecture: separation of NC' and P

more than a real question this is a recap of something i have been studying. I hope someone will help me getting things straight, so any correction or thought about the following reasoning is more ...
0answers
34 views

### Weak PRG to derandomize BPP into DTIME [closed]

Assuming there is a deterministic polynomial time TM M such that on every input 1^m, outputs a((log m)^2, m, 1/10)-PRG. Please show that BPP ⊆[c>1DTIME(2^((log n)^c)))
0answers
39 views

### Error reduction in BPP for other probabilities [closed]

Can someone please explain how the error reduction is done in BPP? Moreover, if • if x ∈ L, then Pr[M(x) = 1] ≥ 4/5; • if x 6∈ L (x does not belong to L) , then Pr[M(x) = 1] ≤ 3/5; How can I prove L ...
0answers
164 views

### anything hinting that EXPTIME $\subseteqq$ PSPACE?

Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？
4answers
2k 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 ...
0answers
52 views

### Additive error approximations of GapP functions

Consider a GapP function $g(x)$ for $x \in \{0, 1\}^{*}$. Consider an approximation $\tilde g(x)$ such that \begin{equation} \left|g(x) - \tilde g(x)\right| \leq \epsilon. \end{equation} Consider a ...
0answers
89 views

### Candidate one way functions and $NC$?

All the known candidate one-way functions are in $NC^1$ (integer multiplication, Iterated modular multiplication (where we are allowed to preprocess generators (of multiplicative group modulo $q$ ...
0answers
151 views

### IP, MIP and MIP* with super-polynomial verifier

Regarding each of the above classes, what are the currently known upper bounds when the verifier is given more than polynomial power? Specifically, when do we reach ALL in each of the above classes ...
0answers
121 views

### Complexity of real coefficients Linear Programs

I would like to know if there are known any polynomial time algorithms for deciding the feasibility of linear programs with real (not integers) coefficients. I know that for linear programs with ...
0answers
71 views

### Improving the approximation in Stockmeyer's counting theorem

Given a $\#P$ function $f(x)$, we can use Stockmeyer's counting theorem to get an approximation $g(x)$ such that \begin{equation} \left(1 - \frac{1}{\text{poly}(n)} \right) f(x) \le g(x) \le \left(...
1answer
213 views

### NLOGTIME versus $\exists$DLOGTIME

$\def\dlt{\mathrm{DLOGTIME}}\def\nlt{\mathrm{NLOGTIME}}\def\mr{\mathrm}$During a recent discussion on another question, I mentioned a factoid $\exists\dlt=\nlt$, but then I realized that I may have ...
0answers
73 views

0answers
70 views

7answers
2k 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 his talk at University of Chicago, note from the talks by Jeremy Kun GLL post 1, GLL post 2, GLL ...
0answers
64 views

### Reference to “compressibility” of logarithmic space [closed]

Is there a reference somewhere for the result SPACE($O(\log n)$) = SPACE($\log n$)? i.e. Big-O doesn't matter in logspace since you can compress the space. I feel like this is an elementary result but ...
1answer
84 views

### Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments

Suppose there is a reduction which, given a $\oplus \text{SAT}$ instance $\phi$, returns another $\oplus \text{SAT}$ instance $\psi$ having all the following properties: The size of $\psi$ is ...
0answers
94 views

### Counting on grid graphs

Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $\#P$ and remain hard for grid graphs? Since there seem to be ...
3answers
441 views

### Hamiltonian cycle vs co-NP [closed]

I am trying to understand co-NP and its implications properly. The French Wikipedia page describing co-NP provides the "complementary" version of the Hamiltonian cycle in co-NP as follows: <...
1answer
138 views

### Complexity of approximating a real function using queries

Consider the following computational problem, where $I$ is the real interval $[-1,1]$: There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of ...
2answers
858 views

### PPAD and Quantum

Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
1answer
113 views

### Is mathematical proof itself NP-hard?

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
2answers
1k views

### Isn't it “trivial” to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks. Isn't it straight forward to ...
1answer
141 views

### Are all RegExp solvable in O(n)?

I'm wondering if all features, that are often part of modern RegEx engines, are solvable in O(n). I'm talking about features like repeating patterns ([abc]+);\1 ...
1answer
353 views

### How “hard” is it to maximize a polynomial function subject to linear constraints?

General Problem Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following ...
1answer
124 views

### Diagonalization arguments for QMA type proof systems

Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, with the essential idea being that of constructing an oracle in ...
0answers
122 views

### Is there an analogue of QMA where Merlin gives Arthur unitaries rather than states?

$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$Is there an analogue to $\mathsf{QMA}$ where Merlin provides to Arthur single-use access to a unitary operator $U$? By ...
1answer
82 views

### Constrained Topological Sorting with bounded number of chains

In general, constrained topological sorting is NP-hard. Now we add another constraint to it, such that take any k+1 nodes and there will be at least one pair ...
0answers
128 views

### Why can MIP be restricted to just two provers?

In several places I see it referred to that the MIP class can be assumed to be two interactive provers that don't communicate with each other, rather than any polynomial number of provers. Why are ...