Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
3,006
questions
5
votes
0
answers
75
views
Why is showing lower bounds for AM communication complexity difficult?
One of the major open problems in communication complexity is to show interesting lower bounds for the Arthur-Merlin (AM) communication complexity of some natural problems (i.e., lower bounds of the ...
- 5,761
0
votes
1
answer
207
views
Is it known that P $\neq$ NP implies BQP $\neq$ NP?
Pretty much the title. Is there any result that shows that $P \neq NP \Rightarrow BQP \neq NP$. I think it's pretty clear that $BQP \neq NP \Rightarrow P \neq NP$, as $P$ is a subclass of $BQP$. But ...
- 1
11
votes
1
answer
797
views
Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?
Recently, I came across the problem of figuring out whether a given binary function $f(x)$ is constant (0 for all values of $x$ or 1 for all values of $x$) or balanced (0 for half of values and 1 for ...
- 113
0
votes
1
answer
70
views
Exchange cards with sum requirement
Given are positive integers $a_1,\dots,a_{2k},b_1,\dots,b_{2k},S$ such that $\sum_{i=1}^ka_i = \sum_{i=k+1}^{2k}a_i = S$ and $\sum_{i=1}^kb_i = \sum_{i=k+1}^{2k}b_i = S$. There are $2k$ cards, card $i$...
CommunityBot
- 1
0
votes
0
answers
41
views
Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?
The following is a well-known result of BPP in complexity theory, e.g., Theorem 1 and its proof from here:
Consider a probabilistic Turing Machine (PTM) $M$, and a language $L \in BPP$:
If $x \in L$ (...
1
vote
0
answers
67
views
What complexity class is characterized by having PSPACE verifiers?
Inspired by the 2 definitions (theorems) I am aware of, that are as follows.
A language L belongs to QMA if there exists
a BQP verifier V.
A language L belongs to NP if there exists a P verifier V.
...
- 890
-3
votes
0
answers
25
views
NP-hard problem between two disjoint points
I have $n$ white points, $m$ black points, and $k$ blue points. Each blue point (i.e., variable) can have a value of 1 or -1. Each blue point can connect a maximum of $c$ edges to white and black ...
- 51
5
votes
1
answer
262
views
Problems complete for non-deterministic PSPACE
Savitch's theorem, i.e. the fact that $NSPACE(f(n)^2) \subseteq DSPACE(f(n)^2)$ implies PSPACE = NPSPACE.
Using the idea of Savitch, Sipser proves in his lectures that TQBF is PSPACE-complete.
What ...
- 5,761
1
vote
0
answers
62
views
Generalization of the Hamiltonian path problem on Grid Graphs
Fix a cost to each of these actions: move up, move down, move left, move right. I.e. fix some function $f: \{\text{move up, move down, move left, move right}\} \to \mathbb N$.
Define the following ...
- 31
5
votes
1
answer
152
views
Functions with polytime iterated applications
Definitions
Let $f : \{0,1\}^n \rightarrow \{0,1\}^n$ be some boolean function where the length of the output always equals the length of the input. Let $f^{k} : \{0,1\}^n \times \mathbb{N} \...
- 1,134
1
vote
1
answer
120
views
A contradiction in the realm of quantum digital and analog computation
It is a well known result that the circuit model of Quantum Computing (QC) is equivalent to the adiabatic model. Furthermore, the former is nothing more than a "slightly" more powerful ...
- 24.3k
3
votes
0
answers
152
views
Is $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$?
It is well-known that $\mathsf{P}\neq\mathsf{SPACE}(n)$, either for $\mathsf{SPACE}=\mathsf{DSPACE}$ or $\mathsf{NSPACE}$, and it is conjectured that both $\mathsf{P}\not\subseteq\mathsf{DSPACE}(n)$ ...
- 131
3
votes
0
answers
94
views
How does NP-completess of decision problems relate to NP-completeness of search problems?
Background
Oded Goldreich differentiates in his textbook (Computational Complexity: A Conceptual Perspective) between the "decision" variant of NP problems and "search" variant of ...
- 2,733
1
vote
0
answers
37
views
Encoding of continuous functions in PPAD
I'm studying the complexity class PPAD (from the seminal 1994 work by Papadimitriou) which contains complete problems such as computing Nash equilibria or finding the fixed point of a Brouwer map. ...
- 2,733
1
vote
0
answers
51
views
Complexity measures for semi-decidable problems
Is there any sensible complexity measure that makes sense to compare the "hardness" of undecidable semi-decidable problems? Time and space are of course not suitable, because they cannot be ...
- 1,558
10
votes
1
answer
290
views
Does $NC=P$ imply the collapse of Polynomial Hierarchy?
If $NC=P$ (with a constructive polynomial time algorithm that converts any $P$ time circuit to a $NC$ circuit), what impact would it have on the rest of the Polynomial Hierarchy?
Couldn't find much in ...
- 1,176
1
vote
0
answers
92
views
If it is $\#{P}$-hard to compute the sign of the permanent of any matrix, does that imply difficulty in relative approximation of the permanent?
I'm trying to understand the statement in the introduction (pg 1) of this work by Anari et all on approximating the permanent $\text{per}(A)$ of a positive semi-definite matrix $A$.
The statement, I'm ...
- 8,866
13
votes
1
answer
844
views
Law of the Excluded Middle in complexity theory
A recent blog post by Lance Fortnow discusses non-constructive proofs, where "non-constructive" here means that the law of the excluded middle is used in a substantive way. That is, one ...
- 27.1k
9
votes
1
answer
293
views
Is P=NP relative to the halting oracle?
Consider the following variant $\mathscr{H}$ of the halting oracle: given the code $e$ for an ordinary Turing machine and an input $n$ to it, we let $\mathscr{H}(\langle e,n\rangle) = \langle 0,0\...
- 2,537
5
votes
0
answers
98
views
Useful notion of ambiguous growing context-sensitive language
As far as I understand there is no useful notion of ambiguous context-sensitive language.
For example for any inherently ambiguous context-free language there is a context-sensitive grammar generating ...
- 5,761
0
votes
0
answers
55
views
Is there a construction which multiplies and adds spanning trees in Logspace?
I.1 Suppose we have two planar graphs $G_1$ and $G_2$ with spanning tree count $C_1$ and $C_2$ respectively then is there a graph construction in Logspace to get a planar graph from $G_1$ and $G_2$ ...
- 12.7k
5
votes
1
answer
288
views
Is Bayes optimal RL of a finite set of DFAs feasible?
Let $Q$ be a finite set of states, $\Sigma$ a finite alphabet, $q_0\in Q$ the start state and $F\subseteq Q$ the set of accepting sets. Let $\{\delta_k:Q\times\Sigma\rightarrow Q\}_{k=1}^n$ be a set ...
13
votes
1
answer
737
views
What is the complexity of (possibly succinct) Nurikabe?
Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid which is to be filled with on/off values for each cell, with each number ...
- 50.8k
0
votes
0
answers
66
views
Sizes of tableau in PH
When one proves that SAT is NP-complete, one uses a tableau of size $n^k \times n^k$. Similarly, when one proves that TQBF is PSPACE-complete one uses a tableau of size $2^{n^k} \times n^k$. Thus, I'm ...
- 919
6
votes
3
answers
305
views
Structural Complexity Theory References
I'm a PhD student in mathematics (mostly studying algebraic geometry), but I've always been interested in computational complexity theory.
As an undergraduate, I completed an independent reading ...
- 11.3k
0
votes
1
answer
55
views
complexity of the maximum rank correlation
Given two sets of vectors of dimension $p$, $x_1,\ldots,x_m$ and $y_1,\ldots,y_n$, The Maximum Rank Correlation estimator is the vector $\beta$ given by $$\arg\max_{b\in\mathbb{R}^p}\sum_{i=1}^m\sum_{...
CommunityBot
- 1
4
votes
1
answer
58
views
Complexity of maximum k-edge-colorable subgraph of a bipartite graph
Can the maximum $k$-edge-colorable subgraph of a bipartite graph be found in polynomial time? Equivalently, can the maximum $k$-colorable subgraph of the line graph of a bipartite graph be found in ...
- 6,979
1
vote
1
answer
100
views
Name and complexity of a stone placement puzzle
Consider the puzzle comprised of $N$ stones. Each stone is given a set of candidate locations. The goal is to put each stone in one of its candidate locations such that no two stones are put in the ...
- 50.8k
1
vote
0
answers
81
views
Complexity of n-rooks completion
I am motivated by the post, Complexity of n-queens-completion. I am interested in completion problem of non-attacking rooks on a chessboard.
Input: Given a chessboard of size $n*n$ with $n-k$ rooks ...
- 20.8k
14
votes
2
answers
1k
views
Space alternating hierarchy
It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions).
In the same paper, Immerman state that the ...
- 105
2
votes
1
answer
228
views
Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?
Let $H = (V, E)$ be a hypergraph, with $V$ the set of vertices and $E \subseteq 2^V$ the set of hyperedges. An elimination sequence on $H$ consists of alternatively removing hyperedges. Specifically, ...
- 8,866
6
votes
1
answer
328
views
Condition Number dependent algorithms for matrix operations
Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
- 4,671
12
votes
1
answer
2k
views
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
- 8,866
1
vote
0
answers
71
views
Using a certificate in the proof of NP hardness
Say I wanted to determine that the problem of membership in some language $L \subseteq \{0, 1\}^*$ is NP-hard. Say that I have a reduction $r: \{\text{set of quantifier free formulas} \rightarrow \{0,...
- 21
2
votes
0
answers
76
views
Status of QNC vs. PSPACE
It is known that $\text{NC} \neq \text{PSPACE}$, now I am wondering if there is a similar separation for $\text{QNC}$, the class of decision problems solvable by polylogarithmic-depth quantum circuits ...
- 890
0
votes
1
answer
221
views
The Complexity of Multi-Objective Optimization
Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors where $v_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d_1\times d}$, the target is to select two subsets $V_1=...
CommunityBot
- 1
3
votes
1
answer
165
views
Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?
I noticed a lot of 1-player games have been shown to be NP-Hard, like Pac-Man, The World's Hardest Game, Tetris, etc.
For PSPACE-Complete, I noticed that Wikipedia listed these 1-player games:
It is ...
- 5,761
2
votes
0
answers
55
views
On the multiplicative overhead 2 in the construction of pairwise independent hashing from ERCs
A standard method of constructing pairwise independent hash function from error-correcting code is as follows:
Given a generator matrix $G$ of a distance-$d$ linear error-correcting code mapping $m$ ...
0
votes
1
answer
130
views
Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?
I am a mathematician and I am very new to theoretical computer science.
The definition of P/NP problem I found in wiki is that:
P is the set of decision problems solvable in polynomial time by a ...
2
votes
1
answer
149
views
Short UNSAT Certificates for X3SAT
Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
- 549
1
vote
0
answers
119
views
Can "dense" SAT instances be solved in time $o(2^n)$?
By "dense" I mean instances in which the ratio of variables to clauses is below the critical threshold $2^k\ln2−\frac{(1+\ln2)}2+\epsilon_k$ for $k$-SAT. For general SAT, however, I suppose ...
- 245
13
votes
2
answers
366
views
General collection with the current state of complexity bounds of well-known unsolved problems?
Most classical computer science problems are still open concerning the exact asymptotic algorithmic worst-case complexity required to solve them.
Is there any online collaborative wiki (or other ...
- 5,761
2
votes
0
answers
42
views
Reducing the amount of alternations without exponentially increasing the runtime?
Let $\mathsf{AltTime}(g(n), f(n))$ denote the class of languages that are solvable by an alternating machine using $f(n)$ time and $g(n)$ alternations.
Is there anything known about the following ...
- 245
3
votes
1
answer
247
views
Is modular square roots modulo primes in $NC$?
Assume modulus is prime. Is modular square roots then in $NC$?
If not then, are there special primes or prime powers or numbers related to these (such as $2^k\pm i$ where $i\in\{-1,0,+1\}$) where it ...
- 16.5k
10
votes
8
answers
1k
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 ...
- 5,761
3
votes
1
answer
119
views
Example of a problem in $P^{PP}$?
Can someone provide an example of (possibly complete) natural problems in the class $P^{PP}$?
we know that MAJSAT is a $PP$ complete problem which is defined as: Given a Boolean formula F. The answer ...
- 16.5k
10
votes
3
answers
479
views
Complexity results for Lower-Elementary Recursive Functions?
Intrigued by Chris Pressey's interesting question on elementary-recursive functions, I was exploring more and unable to find an answer to this question on the web.
The elementary recursive functions ...
- 16.5k
4
votes
1
answer
406
views
Can Lexicographic BFS be implemented in logspace?
Input: Given graph $G=(V,E)$ vertex labeling in some order
Output: Change the labeling of vertices's such that
labeling start $v_1$ as $u_1$, next label the neighbors of $v_1$ as $u_2,u_3,u_4,...$ ...
CommunityBot
- 1
0
votes
0
answers
41
views
What the relation between the classes SC and NC?
What the relation between the classes SC (Scott's class) and NC? (Nick's class).
Is SC contained in NC?
Is NC contained in SC?
- 177
0
votes
0
answers
70
views
Original references for Karp-Lipton theorem improvement by Sipser
The Wikipedia article about the Karp-Lipton theorem ($NP\subseteq P/poly$ implies $\Sigma_2=\Pi_2$), says the following:
The Karp–Lipton theorem is named after Richard M. Karp and Richard J.
Lipton, ...
- 16.5k