Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,650
questions
-5
votes
0answers
29 views
How does 3-SAT necessarily becoming greater-than-3-SAT not prove P != NP? [closed]
So I've done some messing around with 3SAT and I've found some people who have found some of the things I've found. For example:
...
-2
votes
1answer
39 views
the shorstest cycle containing two given points
I am given a edge-weighted (multi)graph $G$ and two of its vertices, $u, v\in V(G)$. I want to find two edge-disjoint paths that connects $u$ and $v$ while minimizing the sum of the lengths of the ...
0
votes
1answer
68 views
Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?
We conjecture that Hamiltonian cycle is fixed parameter tractable with parameter clique cover, given $k$-clique cover.
Let $G$ be connected simple graph.
$k$-clique cover of graph $G$ is partition ...
9
votes
2answers
2k views
“Almost all objects have property P” vs. “It is easy to test whether an object has property P”
I am interested in any relation between "almost all objects(from a universe) possessing a particular property P" versus "testing whether an object has property P being poly. time decidable".
My guess ...
0
votes
1answer
70 views
Is the counting version of 1-in-3 Sat #P-complete?
In the paper "Hard Tiling Problems with Simple Tiles", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat.
Cubic Planar Positive 1-in-...
0
votes
0answers
34 views
Randomized Reduction for Maximization Problem
I have two maximization problems $P_1$ and $P_2$ where the decision version $L_1 = \{(x, t) : \operatorname{Val}_1(x)\ge t\}$ of $P_1$ is $\mathsf{NP}$-complete. Let $f:P_1\to P_2$ be a randomized ...
4
votes
1answer
172 views
+100
Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?
This is another attempt to formalize my former question on the topic.
I'm looking for a problem for which all known classical algorithms take exponential time, but given ANY number of few qubits (...
-3
votes
0answers
58 views
Violating the hierarchy theorems mildly
We know $NC\subsetneq PSPACE$ unconditionally.
Do we know $PSPACE\subseteq NC/log$ is possible?
Do we know $PSPACE\subsetneq NC/log$ is possible?
Likewise take two classes $A\subseteq P$ and $B\...
0
votes
1answer
163 views
Does two-sided error have more capability than one-sided error?
From $P=RP$ extrapolation we might think $EXP=REXP$.
What evidence do we have $BPP\subseteq REXP$?
What consequence $REXP\subseteq BPP$ gives other than what $EXP\subseteq BPP$ gives?
-3
votes
0answers
66 views
How can I prove that a specific structure $\Pi_2$ problem is $\Pi_2$-complete?
The polynomial hierarchy problem is describled as following:
$$\varphi_1:= \forall x_1\forall x_2\cdots \forall x_n\exists x_{n+1}\exists x_{n+2}\cdots\exists x_{n+m}~\bigwedge_{i=1}^n[f_i(x_{n+1},\...
2
votes
0answers
83 views
How fast can we perform DFT on a Log-RAM computer?
The question is how fast we can perform an $n$ coefficient discrete Fourier transform on the log-RAM model of computation. If we assume that we can do arithmetic operations on registers of size $\log{...
3
votes
0answers
82 views
Isomorphic subforest problem
I recently read that the following problem is NP-Complete:
Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$?
The reference provide was to the textbook “Computers and ...
2
votes
0answers
95 views
Witness verifiable quantum advantage
As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results.
If the quantum computer would be powerful enough to solve problems in NP (like ...
6
votes
1answer
361 views
Quantum Money where not even the Bank can counterfeit
The Quantum Money system proposed in "Quantum Copy-Protection and Quantum Money" has the following properties:
The bank can produce bank notes in the form of quantum states.
Anyone can verify that ...
2
votes
0answers
50 views
Can $\mathsf{P}^{\#\mathsf{P}}$ be described in terms of a non-deterministic (alternating) Turing machine?
Can the $\mathsf{P}^{\#\mathsf{P}}$ (= $\mathsf{P}^{\mathsf{PP}}$) class be described in terms of a non-deterministic Turing machine (in particular, an alternating Turing machine)? And would a $\...
1
vote
1answer
70 views
The decision procedure of theory of closed real field is in NP-hard?
The decision procedure of theory of closed real field refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers
2
votes
1answer
47 views
Maximum subgraph problem with unknown complexity
Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem:
Maximum $Q$-...
9
votes
1answer
147 views
What is the complexity of checking equivalence of two boolean formulae without NOT symbol?
Suppose I have two boolean formulae (propositions) $P_1$, and $P_2$ (can be assumed to be in CNF) over the same variables and such that there are no "NOT" symbols used. I.e. only conjunction and ...
9
votes
2answers
111 views
Complexity of finding an edge set yielding specified vertex degrees
I'm trying to figure out if the following two problems are known in general to be in P or NP-complete:
Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'...
4
votes
0answers
121 views
Terminology: FNP, with P replaced by NP?
Consider these two classes of search problems:
Search problems with poly-sized solutions s.t. verifying solutions is in P.
Search problems with poly-sized solutions s.t. verifying solutions is in NP.
...
2
votes
0answers
96 views
Matrix multiplication when one matrix is fixed
Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry
One is allowed to pre-process this matrix as appropriate.
Given another positive integer entried $B$...
5
votes
1answer
265 views
Consequences of BPP=BQP
If BPP=BQP then there is a polynomial time randomized factoring algorithm. A lot of other quantum algorithms that appeared to have an exponential speedup have recently been dequantized. For examples, ...
1
vote
0answers
63 views
Time complexity of alternation free quantified linear program with no free variables and only existential quantifications
We know $\exists x\in\mathbb R^n:Ax\leq b$ is standard linear program.
I am mainly looking at following case of quantified linear program with no free variables with only existential quantifications ...
9
votes
0answers
128 views
What are some examples of algorithmic applications of noncommutative rational identity testing?
The problem of polynomial identity testing (PIT) is known to be in $\mathsf{RP}$, but not known to be in $\mathsf{P}$.
The related problem of noncommutative rational identity testing (NCIT) is known ...
5
votes
1answer
91 views
Is the isomorphism problem between posets represented by DAGs GI-complete?
Given two directed acyclic graphs, how hard is the problem of checking whether the partial orders they represent are isomorphic? Is this problem GI-complete?
I believe this problem is equivalent to ...
5
votes
1answer
198 views
Qubit gates in google supremacy
The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment ...
6
votes
1answer
177 views
Document references describing weaknesses for cutting planes and algebraic proof system?
Here, Fortnow says (section 4.3):
Since then complexity theorists have shown similar weaknesses in a number of other proof systems including cutting planes, algebraic proof systems based on ...
4
votes
1answer
295 views
Which complexity class does this problem belong to?
Consider the following problem $\mathcal{P}$.
Instance: A Boolean formula $F$ of $n$ Boolean variables ($x_1,...,x_n$) and $m$ Boolean parameters ($b_1,...,b_m$) where $0 \leq m \leq n$.
Problem: ...
1
vote
1answer
115 views
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense? [closed]
Note: This has been cross-posted to Quantum Computing SE.
If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies ...
3
votes
1answer
269 views
Complexity classes not closed under intersection and union
Some of the better known complexity classes: PP, NP, P... are closed under intersection and union. What are some counter-examples? Is there a natural reason for the common complexity classes to be ...
5
votes
1answer
225 views
What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$?
What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates?
What is the consequence if there is an $\alpha\in(0,1)$ such that $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates ...
1
vote
1answer
69 views
Are there common names for the subtiers of PTIME?
We all know P, or PTIME, I think, as a common name for the class of polynomial-time problems. Are there common names for the first few levels inside P; that is, for constant-time, linear-time, ...
4
votes
1answer
157 views
On complexity class $\mathsf{\Pi_2 L}$
I suggest the following definition of $\mathsf{\Pi_2 L}$ (similarly to the certificate definition of $\mathsf{NL}$):
A language $L$ belongs to $\mathsf{\Pi_2 L}$ iff there exists a deterministic ...
2
votes
0answers
52 views
Complexity of Block Design?
What is known about the complexity of creating Block Designs (https://en.wikipedia.org/wiki/Block_design)?
I've found one paper that creates approximately solutions using Metaheuristics that claims ...
0
votes
0answers
57 views
Information theory for Mathematical Physics [duplicate]
What are some good introductory texts on information theory for someone who is classically trained in mathematical physics?
Unfortunately my abilities in computer sciences and formal logic are next ...
10
votes
0answers
177 views
On Courcelle's question about Monadic second-order logic with cardinality predicates
I have found the following question at openproblemgarden.org:
The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the ...
-1
votes
1answer
58 views
Chomsky-Schutzenberg Hierarchies explained for physicist (general) [closed]
I am classically trained in physics, however I have been interested in the use of information theory in studying some classical systems.
As someone who is somewhat unfamiliar with the language of ...
4
votes
1answer
190 views
Results comparing BQP and NEXP
Are there oracle results with $$P=NP\neq BQP=NEXP\mbox{ and }P=NP\neq BQP\neq NEXP?$$
Also is there a $PCP$ characterization of $BQP$ like $$PCP(O(poly(n)),1)=PCP(O(poly(n)),O(poly(n)))=NEXP?$$
8
votes
0answers
142 views
A canonical complete problem for EXP and NEXP in terms of formulae
3SAT is a complete problem for NP. TQBF is a complete problem for PSPACE.
Is there direct way to define canonical complete problems for EXP and NEXP in terms of boolean formulae? I have only seen ...
6
votes
1answer
320 views
On theoretical aproaches for solving $\mathsf{SAT}$ in special cases
In what cases $\mathsf{SAT}$ can be solved in polynomial time?
I know two cases: $2$-$\mathsf{SAT}$ and Horn-$\mathsf{SAT}$.
Question 1: Is there a reference with algorithms for solving $\mathsf{...
10
votes
0answers
296 views
Is unary $\Pi_2$-SUBSETSUM coNP-complete?
Consider the following problem:
for given integers $a_1, \ldots, a_{2n}$ and $A$ that are given in unary representation
define is it true that
for every $S \subseteq \{1, ..., 2n \}$ such that $|...
8
votes
0answers
205 views
Conditional separations of $\exists\mathbb{R}$ from $\mathbf{PSPACE}$
As pointed out explicitly by Emil Jeřábek here:
Even with Turing reductions, $\mathbf{PSPACE}=\mathbf{P}^{\exists\mathbb{R}}$ would still be a breakthrough (and completely unexpected) result.
So ...
-2
votes
1answer
151 views
Evidence integer multiplication is in linear time?
After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-...
0
votes
0answers
43 views
Volume computation of special polytopes
I'm interested in computing the volume of a special class of $\mathcal{H}$-polytopes and the complexity of doing so.
I know that in general it is #P-hard to compute the volume of $\mathcal{H}$
-...
4
votes
1answer
108 views
Satisfiability problems with restricted (not bounded) number of occurrences per variable
Intro
It is known that SAT is hard even when restricted to, e.g., formulas with exactly 3 literals per clause and at most 4 occurrences per variable. On the other hand it is easy if there are exactly ...
40
votes
3answers
5k views
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here.
I have asked some people who are ...
9
votes
1answer
289 views
Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?
We think that $\mathsf{PH}$ does not collapse, and that $\mathsf{PP}$ is not in $\mathsf{P}$.
Suppose on the contrary that $\mathsf{PH}$ does collapse, say even $\mathsf{P}= \mathsf{NP}$.
$\mathsf{...
19
votes
2answers
618 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 ...
7
votes
2answers
194 views
Lower bound on pebbling numbers
Out of curiosity, I tried finding the original paper showing that there are graphs that require $n/\log n$ pebbles in the sense of Hopcroft, Paul, and Valiant’s seminal paper “On Time Versus Space”. (...
1
vote
0answers
96 views
How to prove a general convex set is nonempty or empty in polynomial time?
The general convex set should be represented by a set of (generalized) inequalities $f_{i}(x)\leq 0 $ with $ f_{i}(x) $ being convex in $ x $.
I know ellipsoid method and interior method, but I do ...
