Questions tagged [complexity-classes]
Computational complexity classes and their relations
596
questions
1
vote
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 ...
-1
votes
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)))
-1
votes
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 ...
1
vote
0answers
164 views
anything hinting that EXPTIME $\subseteqq$ PSPACE?
Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？
7
votes
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 ...
1
vote
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 ...
0
votes
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$ ...
1
vote
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 ...
3
votes
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 ...
3
votes
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(...
12
votes
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 ...
2
votes
0answers
73 views
Consequences of an $o(\log n)$-approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem
In [1], Feige proves that if there is a polynomial algorithm with approximation ratio in $o(\log n)$ for any $\mathsf{log\textit{-}APX}$ hard problem (say Minimum Dominating Set), then $\mathsf{NP}\...
3
votes
1answer
117 views
What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?
It is known $AC^0[2]$ cannot get majority function.
Is there a literature on simulation of $MAJ$ function utilizing $AC^0[2,3,\dots,p]$ gates for a finite fixed set of primes $2$ to $p=O(1)$?
What is ...
0
votes
1answer
223 views
Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?
If $P=PP$ then the counting hierarchy collapses to $CH=P$. Because so many complexity classes are contained in $CH$, this causes most classes to now be contained in $P$. My question is whether this is ...
0
votes
0answers
66 views
On Determinant modulo $2^k$ complexity
Determinant of integer matrix modulo $2$ is complete for the class $\oplus L$. Is determinant modulo $2^k$ computable in $\oplus L$ at any fixed $k$?
How about if $k=o(n)$ where matrix is $n\times n$?
4
votes
0answers
143 views
The graph of problem reductions
A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
0
votes
1answer
132 views
Comparing SAT to MCSP reduction class separations and faster SAT class separations?
Assume $SAT$ is in $QuasiP$. We immediately infer $NQuasiP=QuasiP$ and $EXP=NEXP$. From https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf we infer $NQuasiP$ is not in $P/poly$ which implies $...
0
votes
0answers
70 views
What is the best reduction we know from flavors of $SAT$ to $MCSP$?
Consider $\mathcal P(n,m)$ to be a class from the set $\{k\mbox{-}\mathsf{SAT}(n,m),\mathsf{CIRCUITSAT}(n,m)\}$ where $k$ is fixed, $n$ is number of variables and $m$ is number of clauses.
Denote $\...
5
votes
1answer
193 views
Where is $MA$ more relevant than $\exists BPP$?
(EDITED)
A previous version of this question asked about a complexity class I called $MA^*$, which has been recognized by users to be $\exists BPP$.
The difference between $MA$ and $\exists BPP$ is ...
0
votes
0answers
51 views
Is anything known about NC$^1$ with NP oracle
A few things are known about the class $\textsf{L}$ provided with an $\textsf{NP}$ oracle ($\textsf{L}^\textsf{NP} = \Theta_2^\textsf{P}$ has attracted a bit of attention, for instance [1]) On the ...
2
votes
0answers
50 views
Logarithmic queries to $\Sigma_i^P$ oracle and the Boolean hiearchies
If I understood correctly (the complexity zoo, wikipedia, and some of the cited articles), the class $\textsf{P}^{\textsf{NP}[\log]}$, also known as $\Theta_2^{\textsf{P}}$, sits at the top of the ...
0
votes
0answers
107 views
$\mathsf{ACC}^0$ and $\mathsf{TC}^0$ with $\mathsf{Cuniform}$-$\oplus\mathsf{L}$ or $\mathsf{Cuniform}$-$\mathsf{NC}^1$ oracle?
$\mathsf{TC}^0$ is a small class with $\oplus\mathsf{L}$ containing it.
Following inclusions are known:
$$\mathsf{Cuniform}\mbox{ -}\mathsf{ACC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\mathsf{TC}^0\...
2
votes
1answer
111 views
Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$? [closed]
A complete problem for $\mathsf{PPP}$ is the pigeon problem which is 'Given a Boolean circuit ${\displaystyle C}$ having the same number ${\displaystyle n}$ of input bits as output bits, find either ...
0
votes
0answers
5 views
Is base conversion in $\mathsf{TC^0}$?
$\mbox{Problem}_{j,i,q}(x_1,\dots,x_n)$: Given an integer $\sum_{i''=0}^{n-1}2^{i''}x_{i''+1}$ in binary output the $j$th binary digit of the $i$th base-$q$ digit (where $q$ is not necessarily a prime)...
5
votes
1answer
223 views
Is there a containment between $\mathsf{ZPP}$ and $\mathsf{UP}$?
Do we know if $\mathsf{ZPP}\subseteq\mathsf{UP}$ known or is there oracles against the hypothesis?
12
votes
0answers
330 views
NP complete problem help
I'm currently trying to find a reduction to this problem:
Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...
39
votes
7answers
6k views
What do we know about provably correct programs?
The ever increasing complexity of computer programs and the increasingly crucial position computers have in our society leaves me wondering why we still don't collectively use programming languages in ...
18
votes
3answers
762 views
In what class are randomized algorithms that err with exactly 25% chance?
Suppose I consider the following variant of BPP, which let us call E(xact)BPP:
A language is in EBPP if there is a polynomial time randomized TG that accepts every word of the language with exactly 3/...
2
votes
0answers
61 views
Is it to solid to conclude APX-complete after showing a problem cannot be approximated better than 1.5 and also develop a 2-approximation algorithm
I know the canonical way to show APX-Complete is to give an L-reduction from an already-known APX-complete problem. If I have used gap-preserving reduction to show a problem cannot be approximated ...
1
vote
1answer
81 views
Can a NEXP machine simulate invalid queries to a promise problem oracle?
Let $A=(A_{YES},A_{NO})$ be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output ...
2
votes
1answer
138 views
What graphs on $\mathbb{N}$ can be encoded as regular languages?
Suppose I represent the natural number 0 by "x", and use the symbol "s" for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers ...
0
votes
0answers
343 views
Unambiguous Problems and Classes over Reals
Are there unambiguous analogues of $NP_{R}$ (using the BSS model, in all discussion)complete problems, and any results known about them? For instance, the canonical $NP_{R}$ complete problem $4FEAS$ (...
18
votes
1answer
1k views
Has parameterized complexity led to better algorithms?
I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...
2
votes
1answer
122 views
Complexity of type inference in the simply typed lambda calculus
A similar question was answered here:
Is simply typed lambda calculus equivalent to primitive recursive functions
What I conclude from the answers is that the complexity is that of the extended ...
1
vote
1answer
65 views
Rademacher Complexity of the Composition with an Indicator
Consider the statistical learning setting where you have an arbitrary hypothesis space $\mathcal{H}$, a data space $\mathcal{Z}$, and a bounded loss function $\ell: \mathcal{H}\times \mathcal{Z} \...
23
votes
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 ...
1
vote
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 ...
1
vote
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 ...
6
votes
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 ...
0
votes
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:
<...
6
votes
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 ...
21
votes
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 ...
-5
votes
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 ...
8
votes
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 ...
3
votes
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 ...
9
votes
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 ...
1
vote
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 ...
5
votes
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 ...
1
vote
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 ...
4
votes
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 ...
