Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,712
questions
-2
votes
1answer
53 views
Hardness of maximizing difference of functions [closed]
Suppose that the problem of maximizing a real function $f$ over a certain domain $D$ is NP-HARD but maximizing $f-g$, with $g$ being another function over $D$, is easy (in PTIME). What can be said ...
-4
votes
0answers
55 views
Has it been proved for any computational problem that it isn't in P? [closed]
i.e. are there any computable problems that are definitely not in P? Even if it's ridiculous to think that it would be in P, are there proofs of this for any algorithm? For example computing the ...
0
votes
1answer
46 views
Common solutions to 3SAT and 2SAT models comprised of the same variables
I have a problem which is a combination of 3SAT & 2SAT instances.
Consider $L$ is a set of variables $(x_1 ... x_n)$. $S_3(L)$ is a 3-SAT instance and $S_2(L)$ is a 2SAT instance, both made of ...
7
votes
1answer
124 views
Isomorphism of ‘ordered’ DAGs / acyclic semiautomata
I am wondering what is known about the isomorphism problem on ordered DAGs, in particular how to find a canonical representative modulo isomorphism.
By ordered I mean that each vertex has a list of ...
5
votes
0answers
78 views
Separating QMA and QCMA
A separation between $QMA$ and $QCMA$ remains a notoriously difficult open problem. Even an oracle separation remains elusive. Have there been any recent efforts towards establishing such a separation,...
1
vote
0answers
40 views
Complement of Multi-colored Clique with an extra condition
In the problem Multi-colored clique, we ask for a $k$-clique of the input graph $G$ where $G$ is guaranteed to be $k$-colorable. In the complement problem Independent Set given Clique Partition, we ...
2
votes
1answer
77 views
Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices
I am interested in the MulitColoredClique problem with an additional restriction.
(Def.: A $k$-coloring $V_1,V_2,\dots,V_k$ of a graph $G$ is a partition of the vertex set of $G$ into $k$ independent ...
4
votes
0answers
99 views
Computational complexity of finding paths with specified product in a (group-labeled) directed graph
This question came up in the analysis of the puzzle game Swish. One way of representing the solvability problem is this: given a directed graph $G$ where each edge of the graph is labeled with an ...
11
votes
1answer
167 views
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
In this talk at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the 3-dimensional Matching (3-DM) problem. In other words, there is a reduction between ...
1
vote
0answers
62 views
Can the theory of Bidimensionality be applied to weighted instances of a problem?
So my understanding of bidimensionality is you are assured the problem solution is about O(k^2) so you can pay O(k) purely to reduce the instance to one of bounded treewidth. As far as I know, this ...
1
vote
1answer
68 views
Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments
Suppose there is a reduction which, given a $\oplus \text{SAT}$ instance $\phi$, returns another $\oplus \text{SAT}$ instance $\psi$ having all the following properties:
The size of $\psi$ is ...
-3
votes
1answer
63 views
tables of reductions in literature [closed]
I'm interested in tables of which problems are reducible to which other problems. Particularly for graph problems, but any such tables/graphs would be neat, just so I know how to look for them. ...
1
vote
0answers
177 views
Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?
In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the ...
6
votes
0answers
79 views
Counting on grid graphs
Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $\#P$ and remain hard for grid graphs?
Since there seem to be ...
21
votes
3answers
5k views
Implications of proving NP=RP on complexity theory
Edit: As indicated below by Mahdi Cheraghchi and in the comments, the paper has been withdrawn. Thanks for the multiple excellent answers on the implications of this claim. I, and hopefully others, ...
2
votes
0answers
48 views
The Edge Cover Equilibrium Problem
Let the Edge Cover Equilibrium Problem be the following:
INPUT: a simple undirected graph $G$.
OUTPUT:
YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
4
votes
0answers
83 views
Complexity of finding the mean of the subset with smallest variance
Let $x_1,\ldots, x_n \in R^d$, and $\alpha \in (0, 1)$. Suppose that $\alpha n$ is an integer.
Let's consider the following problem
$\min_{\mu \in R^d} \frac{1}{n} \sum_{i=1}^n F\left(\frac{\pi(i)}{n}\...
6
votes
2answers
438 views
Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis
In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “...
-2
votes
1answer
138 views
What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?
Unlike hierarchy collapse arguments for classical complexity we have that quantum complexity is different.
What evidences are there that $PP$ is in $BQP$?
What evidences are there that $PP$ is not ...
1
vote
0answers
42 views
Non-rigid isomorphic structures
In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...
6
votes
2answers
276 views
3SUM Complexity—A special(?) Case
In the paper “Consequences of Faster Alignment of Sequences” by
Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of ...
2
votes
0answers
150 views
Why is it difficult for $GCT$ to prove super quadratic lower bound?
We have a quadratic lower bound for the Permanent versus Determinant problem.
Why is it difficult for $GCT$ to improve it?
-5
votes
1answer
100 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
104 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
83 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 (...
12
votes
2answers
359 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}$. (...
5
votes
0answers
173 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
125 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
334 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
82 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
142 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
178 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
67 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
116 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
149 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
60 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?
12
votes
2answers
247 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
34 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
159 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
126 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
79 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
218 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
451 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
332 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
149 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
47 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 ...
