Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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

An oracle that separates BPP from PP?

Is there an oracle that gives $P=BPP\neq NP=PP$?
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?