Computational complexity classes and their relations
2
votes
2answers
53 views
Is there a non-deterministic version of the complexity class PP?
From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?)
4
votes
0answers
47 views
Complexity of fractional SAT
Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $...
-4
votes
0answers
27 views
The big question: does P=NP? [migrated]
I figured it was a shame that one of the biggest open questions in theoretical computer science was not listed here as a question. True, nobody has an answer (probably), but still.
Some might argue ...
4
votes
1answer
153 views
Boolean circuits which correspond to L/poly
Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$.
Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\...
0
votes
0answers
56 views
Proving that a problem is coNP-complete [duplicate]
Let $\le^{p}_{T}$ be the Turing or the Cook reduction and $\le_{m}^{p}$ the Karp-Levin reduction.
I know that to prove a problem $P_1$ is coNP-complete I just need to show that $P_1 \in coNP$ and ...
3
votes
1answer
140 views
Indications that strengthen the conjecture: NEXP ⊊ EXP^NP
I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP.
Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper.
Some Examples:
1. A paper by Shuichi ...
3
votes
1answer
165 views
Conesequences of $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$
Does $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$ has any separation of classes or consequences?
My main question is can use this to show that $P \neq NP$ or some thing useful ...
15
votes
0answers
400 views
An algebra of complexity classes
A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes.
For ...
10
votes
1answer
182 views
Is this game EXPSPACE-complete?
Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be ...
4
votes
1answer
64 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 ...
4
votes
1answer
218 views
Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?
Is it known that $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?
5
votes
1answer
308 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 ...
6
votes
1answer
134 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 ...
4
votes
1answer
142 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
87 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
192 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
45 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
108 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
175 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
68 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
48 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
99 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
84 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
117 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
120 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]$?
5
votes
1answer
267 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
444 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
263 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
291 views
What are the problems in EXPSPACE \ EXPTIME?
Based on the diagram below (from Papadimitriou's book) we can see that PSPACE ⊆ EXPTIME ⊆ EXPSPACE. We know that PSPACE ⊊ EXPSPACE, which means that there are problems that can be solved in polynomial ...
0
votes
1answer
70 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
180 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
163 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
446 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
69 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
703 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
53 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
356 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
119 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
125 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
189 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
119 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
87 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
59 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 ...
