Computational complexity classes and their relations
4
votes
1answer
40 views
Complexity of type-checking in relation to complexity of normalization
In order to verify that a terminating program terminates, one thing that can be done is to actually run the program. That may take a lot of time. If the program is typed in a total type-system, we can ...
2
votes
0answers
136 views
Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?
Is it known that $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?
5
votes
1answer
294 views
Can one do quantum computing without negative amplitudes?
The typical representation I see of $k$ qubits is a $2^k$ complex numbers $c_i$ for every possible combination of values of those bits, such that the sum of all the squared magnitudes of those numbers ...
5
votes
1answer
127 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 ...
-6
votes
0answers
70 views
Is the hypothesis RP = NP consistent with known results in complexity theory?
We will consider a particular NP complete problem, 3SAT. Our hypothesis H states that there is a randomized algorithm A, such that for any 3SAT instance (if it has a solution ), the randomized ...
4
votes
1answer
135 views
How powerful is POSIX regex
The set of languages recognized by POSIX regex is a true superset of type 3 languages. But how powerful is POSIX regex really? Is it in an already known class? Is it its own class? If so, what is the ...
1
vote
0answers
83 views
An explicit hard function for P/poly
It is known that $\textbf{MA}_{\textbf{EXP}} \not\subset \textbf{P/poly}$. Is it known any explicit language from $\textbf{MA}_{\textbf{EXP}}$ that does not belongs to $\textbf{P/poly}$?
(An example ...
6
votes
1answer
177 views
What are the consequences of solving XOR 3-SAT in Logspace?
XOR Formulas
Consider boolean formulas with connectives $\wedge$ (AND) and $\oplus$ (XOR). Such a boolean formula is a valid instance for XOR SAT if it is a conjunction of $\oplus$-clauses. An $\...
0
votes
0answers
42 views
What is the best approximation and exact algorithm for vertex cover on cubic graphs?
"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
2
votes
0answers
105 views
BQNC and Abelian Hidden Subgroup Problem
We know integer factorization is in $BPP^{BQNC}$ from Cleve and Watrous.
Is Abelian Hidden Subgroup Problem also in $BPP^{BQNC}$? If not what is it that makes integer factorization special?
In ...
2
votes
0answers
169 views
Primality in $NC$ hierarchy?
AKS primality testing solves whether a given integer is prime in $P$. AKS algorithm is following:
Input: integer n > 1.
Check if $n$ is a perfect power: if $n = a^b$ for integers $a > 1$ and $b &...
0
votes
1answer
66 views
Is Prime Bounded Quadratic Congruence NP-complete?
Bounded Quadratic Congruence:
Instance: Three positive integers $a$, $b$ and $c$.
Question: Is there a positive integer $x<c$ such that $x^{2} \equiv a \, (mod \ b)$?
Bounded Quadratic ...
1
vote
0answers
47 views
An alternative characterization of some NExp-Time Turing machine with oracles
Let me denote by $\Sigma_i^P$ be a class from i-th level of polynomial time hierarchy (see eg. PH).
I'm interested in the following type of a Turing Machine $\mathcal{M}$:
$\mathcal{M}$ is ...
1
vote
0answers
88 views
Is there any NC-complete problem with respect to logspace reduction?
The question is on the title.
We all know that $\text{NL}$ and $\text{P}$ have such problems. So I wonder the same thing about $\text{NC}$. More interestingly, is there any $k \ge 2$ and any $\text{...
8
votes
1answer
81 views
$BPL$ with polylog random bits is in $L$
Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$.
My question is ...
2
votes
1answer
112 views
Best $\Pi_k \text{SAT}$ running time?
Define $\Pi_k \text{SAT}$ by 'Given a quantified boolean formula $\varphi = \forall y_1\exists y_2\dots Q_ky_k\mbox{ }\phi(y_1, \dots, y_k)$,
where $\phi(y_1, \dots, y_k)$ is boolean predicate with ...
3
votes
0answers
118 views
What are the consequences if $W[i]=W[i-1]$?
$FPT=W[1]$ does not collapse the $W$ hierarchy however falsifies $ETH$ belief. Is there non-trivial consequence if $W[i]=W[i-1]$ and any other consequence at $W[1]$?
3
votes
0answers
190 views
Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$?
Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$?
This question came up while watching "Graduate Complexity at CMU - Lecture 2: Hierarchy Theorems (Time, Space, and ...
1
vote
0answers
100 views
Proof of Sipser-Lautmann Theorem
I have written the following answer as an attempt to prove a variation of Sispser-Lautmann theorem, but it was rejected without any comments. I would appreciate if anyone can find the flaws in this ...
1
vote
0answers
36 views
Monotone complexity of PLP
Blum and Nisan show Positive Linear Programming could be done in $NC$ if we only ask for approximate solutions. This paper https://pdfs.semanticscholar.org/8dc7/5aa9d72864022d848c3e599c5f24d9d527e7....
0
votes
1answer
73 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 ...
3
votes
3answers
432 views
Why is the circuit class AC0 unavoidable?
Take AC0.
What is a natural thought process that leads to the definition of AC0?
Does this class arise intrinsically anywhere?
My problem is that in the case of unbounded fan-in, AND and OR gates ...
1
vote
2answers
207 views
Efficiently computable by a “simple” algorithm?
I am interested in the relation between "program complexity" and "computational complexity".
In particular, I was wondering
What is known about the minimal length a program must have to solve a ...
7
votes
4answers
260 views
What are semantic classes that have a syntactic equivalent?
This question is related to Benefits for syntactic and semantic classes.
As mentioned there, $\mathsf{PSPACE} = \mathsf{IP}$, which can be interpreted as the semantic class $\mathsf{IP}$ obtaining a ...
0
votes
1answer
170 views
What are the problems in EXPSPACE \ {NEXP ∪ co-NEXP}?
Based on the diagram below (from Papadimitriou's book) we can see that PSPACE ⊆ EXPTIME ⊆ {NEXPTIME ∪ co-NEXPTIME} ⊆ EXPSPACE. We know that PSPACE ⊊ EXPSPACE, which means that there are problems that ...
0
votes
1answer
69 views
Reduction from SAT to binary matrix subset problem
I'm trying to understand the answer by @Denis on this question, where he showed a way to reduce from SAT to the binary matrix column subset selection problem. The reason I'm having to post a new ...
1
vote
2answers
176 views
If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?
NP-hard problems are not used in cryptography, because they are believed to be computationally-intractable in the worst case but are not computationally-intractable in the average case.
Is there a ...
5
votes
0answers
161 views
Find a pair of nodes with maximum sum of distances in k given trees
For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
11
votes
1answer
441 views
Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?
Imagine we have two size $m$ sets of points $X,Y\subset \mathbb{R}^n$. What is (time) complexity of testing if they differ only by rotation?: there exists rotation matrix $OO^T=O^TO=I$ such that $X=OY$...
1
vote
1answer
66 views
PromiseBQP and expectation values of operators
This question is regarding The Equivalence of Searching and Sampling by Aaronson. In page 4 he makes the following statement,
... a difficult and unsolved meta-question is whether PromiseBPP = ...
5
votes
2answers
692 views
Isn't it trivial to represent any classical Physics problem in a Spin-Glass format which is NP-Complete?
In the late 80's there were several efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks.
Wouldn't it be straight forward to reduce ...
1
vote
0answers
52 views
Kolmogorov generic oracle
In Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?, authors defined a new type of generic oracles named Kolmogorov generic oracles.
They proved following results relative to $...
8
votes
1answer
350 views
Complexity of modal logic IK5
What is the complexity of local satisfiability problem for modal logic $\mathit{IK5}$? Herein we denote by $IK5$ the modal logic over euclidean frames extended with inverse modality. Could you provide ...
0
votes
0answers
63 views
Using idea of entropy (maybe Shannon entropy or other continuous entropy) to the topic of functional analysis
I am an electrical engineer without a detailed background in theoretical computer science. I am posting here since I hypothesize that the concept of entropy or other branches of information theory (as ...
1
vote
0answers
85 views
Does the NP-hardness of finding any valid solution imply NPO-hardness?
Suppose we have an NP optimization problem $A$ such that the problem of finding any valid solution, regardless of whether it is good or bad, is NP-hard (as it happens in NPO-complete problems such as ...
-5
votes
1answer
115 views
Should GCT focus on $PSPACE\not\subseteq P/poly$?
GCT tries to show $P$ is not $NP$ by showing $NP$ is not in $P/poly$.
Could it be useful in showing $\Sigma_{i+1}\not\subseteq P^{\Sigma_i}/Poly$ at every $i>0$?
Suppose if it turns out that $\...
10
votes
1answer
122 views
On sparse complete sets and P vs L
Mahaney's Theorem tells us that if there is a sparse $NP$-complete set under polynomial-time many-one reductions, then $P = NP$. (See "Sparse complete sets for NP: Solution of a conjecture of Berman ...
3
votes
0answers
75 views
How to charactorize computational complexity based on finding solution to algebraic equations? [closed]
The Matiyasevich/MRDP Theorem relates two notions:one from computability theory, the other from number theory, thus Turing Machine and algorithms finding integral solution to algebraic equations can ...
1
vote
1answer
185 views
Relation between transcendental numbers and computational complexity?
Regarding the relation, there is the Hartmanis-Stearns conjecture, but beyond Turing Machine of the realtime output, there is no further conjecture or theorem. Obviously irrational algebraic number ...
7
votes
1answer
118 views
Presburger arithmetic: is it known to be in $EXPSPACE \setminus EXP$?
My understanding of the Presburger arithmetic decision problem is that it requires doubly-exponential time, but only singly-exponential space, meaning that it is in $EXPSPACE \setminus EXP$. ...
2
votes
0answers
84 views
Random self reducibility and NP
I was reading the Wikipedia page https://en.m.wikipedia.org/wiki/Random_self-reducibility and it states: "If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy ...
2
votes
0answers
57 views
On reduction between two classes?
https://link.springer.com/article/10.1007/s00153-013-0351-x gives seven reductions $m,c,d,p,btt(1),\ell,tt$.
What does norm $1$ mean in $btt(1)$?
Is there illustrative examples that help understand ...
0
votes
0answers
133 views
2
votes
1answer
93 views
What is conjunctive truth table reduction?
What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?
9
votes
0answers
88 views
Problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$
Do we know of any problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$?
Context: based on Josh's answer to this question, it could be possible that all ...
1
vote
1answer
58 views
Recursively presenting or even enumerating all P-hard languages
A class of languages $C$ is recursively presentable if there is an effective enumeration of Turing machines $\mathcal{M}_1,\mathcal{M}_2,\ldots$ such that $C=\{L(\mathcal{M}_i)\mid i=1,2,\ldots\}$. ...
4
votes
2answers
239 views
On $NP$, $\oplus P$ and $PP$?
We know $\oplus P^{\oplus P}=\oplus P$, $PP^{\oplus P}\subseteq P^{PP}$ and $NP\subseteq PP$.
Is $\oplus P^{PP}=PP$?
Why is it difficult to show $NP^{NP}\subseteq PP$?
What is the smallest known ...
2
votes
0answers
35 views
A class of languages admitted by a class of grammars equivalent to $\mathbf{PR}$?
Is there a class of languages $L(G)$ admitted by a class of phrase structure grammars $G$ equivalent to $\mathbf{PR}$? (the class of primitive recursive languages = $\mathbf{LOOP}$)?
In greater ...
-1
votes
1answer
130 views
Two queries related to Toda
Is the Isolation lemma crucial for $PH\subseteq BPP^{\oplus P}$ theorem and would avoiding the Isolation lemma say anything more that is not known?
0
votes
0answers
16 views
Are $BPP^{BPP^{\oplus P}}$ and $BPP^{NP}$ contained in $BPP^{\oplus P}$?
Does $BPP^{NP}\subseteq\Sigma_k^P\cap P/poly^{NP}\subseteq BPP^{\oplus P}$ hold at some $3\leq k$?
Also is $BPP^{BPP^{\oplus P}}\subseteq BPP^{\oplus P}$ known?
