Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,634
questions
-3
votes
0answers
59 views
Complexity theory in non-TM models and randomness and complete problems? [on hold]
What are some of the non-TM models considered in complexity theory?
How is randomness introduced in these models and what are the analogs of the SATISFIABILITY problem in these models?
-4
votes
0answers
38 views
Polynomial reduction [closed]
I have two languages $ A \subseteq \Sigma$* and $B \subseteq \Gamma$*
Is it correct that $A\le_P B$ is valid only if $A^C \le_P B^C $.
C stands for complement.
-1
votes
0answers
31 views
Understanding Computability of a Function
I know that computability is the proof of existence of an algorithm to solve a particular function in a infinite time but I can not understand how to decide that it is computable.
How can we know ...
5
votes
0answers
57 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 ...
-4
votes
0answers
56 views
An algebro-combinatorial argument that P = NP [on hold]
Also asked in normal CS stack exchange.
I have long been fascinated by this question and recently wrote an article about it. The version of computation described in the article is similar to those ...
4
votes
1answer
77 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 ...
3
votes
1answer
170 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 ...
-5
votes
0answers
49 views
Why is the Boolean Satisfiability Problem (SAT) so hard to solve?
Please could someone explain to me, fairly simply, why this problem is so hard to solve.
I'm not referring to NP-hard when I say 'hard' but why has no-one solved this problem yet
5
votes
1answer
171 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
274 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: ...
-2
votes
0answers
17 views
Vertex k-coloring on Weighted 3-regular Graph allowing Conflict Edges
Given a 3-regular graph with weighted edges (with the signs being positive). Consider the following decision problem:
Is there a way to color the the vertices with $k$ colors such that the sum of the ...
1
vote
1answer
104 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
251 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
190 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
65 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
149 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
51 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
56 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
171 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
181 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
132 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
315 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
292 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
203 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
139 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
41 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
103 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 ...
39
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
281 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{...
10
votes
2answers
459 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
189 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 ...
8
votes
1answer
222 views
3-coloring planar graphs in $O\left(3^{n^.5}\right)$?
I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from ...
6
votes
0answers
183 views
Nondeterminstic Linear Time vs Other Complexity Classes
Is it known whether or not nondeterministic linear time contains $P$ and/or smaller classes such as Uniform-$NC^1$?
10
votes
1answer
615 views
A game on several graphs
Consider the following game on a directed weighted graph $G$ with a chip at some node.
All nodes of $G$ are marked by A or B.
There are two players Alice and Bob. The goal of Alice (Bob) is to ...
3
votes
1answer
83 views
Complexity of existence of simple polygonalization with prescribed area?
This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
8
votes
1answer
1k views
On the sensitivity conjecture?
The recent establishment of the relation $bs(f)=O(s(f)^4)$ goes through Gotsman,Linial .
Can the same approach get to $O(s(f)^2)$ or is there an essential limitation to the approach?
14
votes
0answers
165 views
Counting solutions to extended MSO formulas, and sampling — do these appear in the literature?
I am trying to determine if the literature contains various extensions of Courcelle's theorem. Since I haven't been able to find these in the literature, I guess that these are folklore results, or ...
2
votes
0answers
116 views
Sensitivity and Low-Degree Approximation under Non-Uniform Distribution
I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
4
votes
2answers
149 views
reference request for construction of expanders
I'm looking for a good exposition of the explicit constructive proof of the existence of expander graph families due to Reingold Vadhan and Wigderson. Arora/Barak has a chapter on it, but i find it ...
2
votes
0answers
79 views
Is there any research on the complexity of producing given a problem description?
It is straightforward enough to analyze the complexity of a particular algorithm as a function of input size or other variables in terms of runtime or space used or whatever else. I am wondering if ...
6
votes
1answer
99 views
Separation of AM and SZK
Are any results on the separation of AM from SZK known (e.g. relativized separation, or a separation assuming one-way functions exist, etc.)?
9
votes
1answer
319 views
Hidden Constants in Complexity of Algorithms
For many problems, the algorithm with the best asymptotic complexity has a very large constant factor that is hidden by big O notation. This occurs in matrix multiplication, integer multiplication (...
2
votes
1answer
148 views
Possibility of hierarchy with $UP$ class?
I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The ...
-1
votes
1answer
254 views
What is the reason to use NP instead of EXP as 'the' class of intractable problems?
What is the rationale for not using EXP has the main class for intractable problems but NP? Why is it important that solutions are verifiable in polynomial time?
9
votes
4answers
328 views
Bootstrapping results that really bootstrap
There is a type of results in TCS usually called bootstrapping results. In general, it is of the form
If proposition $A$ holds, then proposition $A'$ holds.
where $A$ and $A'$ are propositions ...
1
vote
0answers
47 views
Bipartite formula complexity lower bound
I'm trying to understand the paper The Bipartite Formula Complexity of Inner Product is Quadratic, by Avishay Tal. The argument is recapped here. I am having trouble understanding the proof Theorem 3 ...
2
votes
0answers
83 views
Is equivalence of uniform AC0 decidable?
Is there a representation of the functions from $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ for which equivalence is decidable?
Since the languages defined by nondeterministic pushdown automata ...
5
votes
1answer
139 views
Is sorting pairwise distances as hard as sorting arbitrary points?
If we have $n$ points in $\mathbb{R^d}$, what is the complexity of sorting the $O(n^2)$ pairwise distances?
Clearly the complexity is $\Omega(n^2)$ but is there a reduction to show it is as hard as ...
