Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,695
questions
-2
votes
0answers
45 views
Probabilistic exponential time [closed]
Is it somewhat explored the exponential time complexity of bounded error probabilistic algorithms?
Is there a name for the exponential analogue of BPP?
In particular I wonder if it can be proved that ...
0
votes
0answers
63 views
Why is it difficult for GCT to prove super quadratic lower bound?
We have a quadratic lower bound for the Permanent Determinant problem. Why is it difficult for GCT to improve it?
-3
votes
0answers
62 views
Is mathematical proof itself NP-hard?
At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
0
votes
0answers
55 views
Complete problems for dtime
$P$ is the polynomial time class defined as $$\cup_{i=0}^{\infty}DTIME(n^i).$$ which has linear programming as complete problem.
Are there complete problems under linear time reductions within each $...
0
votes
0answers
92 views
Can you diagnolize without mentioning simulation?
Are there any known diagonalization proofs, of a language not being in some complexity class, which do not explicitly mention simulation?
The standard diagnolization argument goes: here is a list of ...
3
votes
0answers
75 views
Are there enumerations of machines for all languages in 𝑃 such that there exists a simulator that can efficiently run all the machines enumerated?
From Kozen INDEXINGS OF SUBRECURSIVE CLASSES: "the class of polynomial time computable functions is often indexed by Turing machines with polynomial time counters.... The collection of all (...
11
votes
2answers
256 views
Complexity relative to the graph of the Busy-Beaver function
This question is inspired by the comments made on this other question that I asked, and by an attempt to provide an explicit example of a complexity question beyond the Turing degree $\mathbf{0}$. (...
0
votes
0answers
64 views
Does $NP \subset BQP$ Imply $Co-NP \subset BQP$? [closed]
Does $NP \subset BQP$ Imply $Co-NP \subset BQP$?
I now that $NP \subset BQP$ does not imply $PH \subset BQP$ But I’m not sure about $Co-NP$.
5
votes
0answers
160 views
Has there been any development of complexity theory for other Turing degrees than 0?
(I'm not sure if this question is better suited for MathOverflow or here. I'll try here first, and move over to MO later if it appears to be more appropriate.)
Complexity theory can be very broadly ...
15
votes
7answers
3k views
In the neutral zone between polynomial and sub-exponential
What are examples of problems that are known to be sub-exponential, but
are known to be non-polynomial, or
are not known to be polynomial?
EDIT. Here is what I mean by sub-exponential (apologies for ...
-4
votes
1answer
118 views
Is there an algorithm for 3x3 sudokus without backtracking? [closed]
From what I can see on Wikipedia and the Internet at large, all sudoku solving algorithms (including human ones) employ some kind of EXPTIME backtracking search for some sudokus.
Are there any SAT ...
8
votes
1answer
312 views
Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?
Fix a deterministic finite automaton $A$ defining a regular language on the alphabet $\Sigma = \{0, 1\}$, and call the (Hamming) weight of a word $w \in \Sigma^*$ its number of $1$'s. Given a length $...
1
vote
1answer
78 views
Choosing one number from each set so that the sum of squares of each distinct number counts is minimized
Problem is as follows:
We are given $K$ subsets of $\{1,2,...,n\}$. We need to pick one number from each of these subsets such that $\sum_{i=1}^n p_i^2$ is minimized where $p_i$ is the number of times ...
2
votes
2answers
139 views
Adjective for: algorithm that outputs its input if it is one of its outputs?
Is there a well established adjective or name for an algorithm such that, given as input any of its own output, always outputs it unchanged? In other words, an algorithm such that it implements a ...
-1
votes
1answer
176 views
Conjecture about ASP reductions between NP-complete problems
$ASP$-complete reductions, introduced by Ueda and Nagao, relate the hardness of computational problems in $FNP$. Basically, $ASP$-reduction is a polynomial time reduction between instances and a ...
1
vote
2answers
63 views
Disjoint subsets problem complexity
Is the decision problem below NP-complete?
Given sets $S_1, ... , S_n$, as well as bounds $b_1, ... , b_n$, is it possible to pick pairwise disjoint subsets $U_1, ... , U_n$ such that $U_i \subset ...
1
vote
1answer
106 views
Diagonalization arguments for QMA type proof systems
Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, with the essential idea being that of constructing an oracle in ...
0
votes
0answers
26 views
Encrypt an explicit circuit
Suppose we are given a circuit that are promised to be in a fixed class $\mathcal{C}$ (say AC^0). We want to “encapsulate” the circuit such that the resulting circuit computes the same function, while ...
5
votes
2answers
145 views
Topological sorting of a DAG where special vertices have to come in even groups
Consider the following problem. The input is a directed acyclic graph (DAG) $G = (V, E)$, and a subset $V' \subseteq V$ of vertices, which we call special vertices. The question is to determine ...
-5
votes
1answer
58 views
We know that X3C is NP-complete with |X|=3q and |C|=m. Is this problem still remains NP-complete if |C|<2q? [closed]
Exact-Cover-by-3Sets (X3C) is NP-complete.
If the number of classes i.e. |C|<2q then whether this is version of X3C is NP-complete or not?
11
votes
2answers
234 views
Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?
There are assumptions that are known to imply that $P = BPP$. For example, if there exists a function in $E = DTIME(2^{O(n)})$ that has circuit complexity $2^{\Omega(n)}$, then $P = BPP$ [1]. Clearly, ...
1
vote
0answers
33 views
Efficient algorithm for finding segregators in a directed acyclic graph
Given a directed acyclic graph $G=(V,E)$, we define a $(\alpha,\beta)$-segregator of $G$ to be a subset $S$ of $V$ of size $\alpha$ such that no vertex in $G\setminus S$ has more than $\beta$ ...
7
votes
1answer
147 views
Complexity class of efficient streaming algorithms
Consider the class of problems $\mathsf{StreamL}$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words:
$L \in \mathsf{StreamL}$ if there ...
3
votes
1answer
108 views
What is FO(REGULAR)? (The descriptive complexity equivalent of NC1)
According to Immerman's Descriptive Complexity diagram, there is a logic called $\mathsf{FO(REGULAR)}$ which captures $\mathsf{NC}^1$. However, I can't find the reference where this logic is defined. ...
9
votes
0answers
116 views
Is 4-in-a-row PSPACE-complete?
This paper by Laurens Kuiper shows that axis-parallel k-in-a-row is PSPACE-complete in complexity for k ≥ 5, but leaves the question open for k = 4. Has there been any research progress on this ...
3
votes
1answer
78 views
What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper
I have been going through Kempe-Kitaev-Regev's paper The Complexity of the Local Hamiltonian Problem. In the first paragraph of page 3, the authors point out that:
To the best of our knowledge, ...
0
votes
1answer
191 views
Time complexity for multiplying two lower triangular matrices
I was wondering, if multiplication of two $n \times n$ lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general $n \times n$ matrices?
$$
\begin{bmatrix}
...
2
votes
0answers
107 views
Proof systems induced by NP-complete problems
Satisfiability is the fundamental NP-complete problem. Cook-Reckhow theorem states that the existence of a propositional proof system that admits polynomial size proofs for all tautologies implies ...
11
votes
3answers
446 views
Applications of sunflower lemma in theoretical computer science
In one lecture by Kewen Wu who is one of the authors of paper
Improved bounds for the sunflower lemma,
it is said that the sunflower lemma can be applied to many fields like
circuit lower bounds
...
7
votes
1answer
326 views
Technical lemma about curves used in original proof of PCP theorem
I am reading the proof from here and found a technical lemma that seems to be incorrect (its proof is short and very vague). I know this is rather specific and the context is problematic, but I couldn'...
5
votes
0answers
143 views
What research is being done in classical complexity theory?
As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as ...
0
votes
0answers
46 views
Can we multiply two numbers more efficiently (using binary circuits) if one of the numbers is fixed? [duplicate]
Let $a_1, a_2 \dots$ be a sequence of natural numbers, where $a_i$ has bit length $i$. Consider a function $f_n : \{0, 1\}^n \to \{0, 1\}^{2n}$ defined as $f_n(x) = a_n \cdot x$ ($\cdot$ is ...
2
votes
0answers
96 views
Is PP invariant under changing its cut-off from 1/2 to another number?
Suppose I have a fixed family of quantum circuits $\{C_i\}$ for which determining whether the maximum output acceptance probabilities are $p\geq 1/2$ or $p< 1/2$ is PP-hard.
Now suppose I have the ...
0
votes
2answers
108 views
Order of quantifiers in the definition of NP-completeness: does the reduction allow arbitrary polynomials? [closed]
Arora and Barak define NP-completeness as the following:
"We say that a language $A \subseteq \{0, 1\}^∗$
is polynomial-time Karp reducible to a language
$B \subseteq \{0, 1\}^∗$
denoted by
$A \leq_p ...
6
votes
1answer
137 views
Is $L \subset 1NL$ when $L \neq NL$?
A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
0
votes
0answers
82 views
Are there complexity theory consequences of the collapse NEXP=EXP^NP?
It is clear that $NEXP\subseteq EXP^{NP}$, as a TM with exponential run time can simply query the NP oracle with an exponentially long query. However, it's not clear that the reverse $EXP^{NP}\...
2
votes
0answers
95 views
Complexity of a scheduling problem with a fixed left bound of jobs
Consider the following scheduling problem. We have a finite set of jobs $\mathcal{J}= \{j_1, j_2, ..., j_n\}$ to do. Every job $j_i$ has its own value $c_i$ (the amount of money we are paid for ...
2
votes
1answer
105 views
What is the computational complexity of Acyclic Joins?
I am quite new to relational algebra, but I realize that there are efficiency proofs for processing Acyclic joins. I have not been able to understand these results, but this particular problem is ...
7
votes
5answers
392 views
NP-complete decision problems on deterministic automata
Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
2
votes
1answer
56 views
FO(TC) lower bounding games?
Is anyone aware of any games/algebraic structures that provide lower-bounding methodologies for $FO(TC)$ formulae? I am aware of EF games as they apply to first-order and second-order statements, but ...
1
vote
0answers
70 views
existence & characterization of “kolmogorov efficient” programs
$\newcommand{\Prog}{\operatorname{Prog}}\newcommand{\kol}{\operatorname{kol}}$
Disclaimer: I do not have a formal background in algorithmic complexity theory so apologies if I use non-standard ...
3
votes
1answer
116 views
$DTIME_1(o(n^2))\setminus$ REGULAR
Maybe this is well-known, but I couldn't find any example of a non-regular lanugage that is decidable on a single-tape Turing machine in subquadratic time.
Help!
Related paper: On the structure of ...
10
votes
0answers
138 views
Alternative proofs of Savitch's theorem?
Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one?
By the usual one I mean the proof based on recursively querying whether there is a midpoint.
...
2
votes
1answer
112 views
Complexity of solving systems of linear equations with hash preimages
Introduction: I'm researching a decision problem that I thought was in NP because there are certificates for its instances that have a polynomial number of elements. However, I realized that there are ...
1
vote
1answer
54 views
Matrix rank approximation
I am aware of the problem of low rank approximation of matrices which has been studied in various models of computation. My question is the following:
What is the status of approximating rank of a ...
5
votes
1answer
132 views
Complexity of finding automorphism group of code
What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code?
Is there better bound on complexity if structure of code is known for ...
2
votes
1answer
160 views
Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?
Background
It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$.
Although some natural problems are known to exist, many of them ...
2
votes
2answers
168 views
Problem in deterministic time $n^p$ and not lower
I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable).
...
7
votes
1answer
145 views
The complexity of the permanent of low rank matrices
I know that for an arbitrary $n \times n$ matrix, Ryser's algorithm can compute the permanent in $\mathcal{O}(2^n n^2)$ time. I'm interested in computing the permanent of $n \times n$ matrices of rank ...
-1
votes
1answer
68 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 ...
