Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
3,019
questions
0
votes
0
answers
21
views
How often can a clause cause a conflict?
This question is about DPLL+CDCL algorithms. How often can a clause cause a conflict?
I want to use a specific algorithm. Assume a DPLL+CDCL SAT solver using a fixed variable order. Variables and unit ...
- 549
8
votes
1
answer
349
views
What can we do with a generic oracle (as opposed to a random one)?
Let me first recall a few (lengthy but hopefully mostly standard) facts and definitions in order to motivate my question (feel free to skip down to the actual question):
Standard definitions: A ...
- 619
-1
votes
0
answers
77
views
Proof for Upper Bound on the Size of the Sum of Rational Numbers
In [1], Dominik Wojtczak determines that the 0-1 SUBSET-SUM problem with non-negative rational numbers is strongly NP-Complete.
Assume we are given a list of n items with
rational non-negative ...
1
vote
1
answer
122
views
Are there any algorithms that the brain is better at solving than a regular computer? How would these be found/verified?
For example, one that brains appear to be able to solve in polynomial time but computers can't, or one optimized for the brain's innate capabilities - like language learning, or different ...
- 11
-1
votes
0
answers
24
views
Finding an algorithm EF[1,1] and PO division for more than two agents
From this research paper I want to write an algorithm for finding envy-freeness(EF) and Pareto optimality(PO) division for more than two agents.
We consider the problem of fairly and efficiently ...
- 99
1
vote
0
answers
63
views
Crafting ${NP}^{\#P}$-complete problems
Some related posts:
Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?
$\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$
I needed a complete problem for the class ${NP}^{\#P}$ for a reduction to show the hardness of some other ...
- 11
0
votes
0
answers
16
views
Any value in a formula that calculates (not look up) the 'order' of a 'Independent Edge Set' OR a 'I.E.S.' given an 'order' on complete graphs?
Any value or interest in a formula that calculates (not look up) the 'integer order' of a given 'Independent Edge Set' OR given an 'Independent Set' calculates the 'integer order' on Complete Graphs? ...
- 1
3
votes
1
answer
344
views
Intuition on Lupanov's Upper Bound on Circuit Size
The following result, by Lupanov, is a classic in the theory of Boolean function complexity:
Theorem: For every boolean function $f$ of $n$ variables:
$$C(f) \leq (1 + \alpha_n)\frac{2^n}{n}, \text{ ...
- 133
-3
votes
1
answer
98
views
Can one do descriptive complexity theory using abstract state machines?
I learned about ASM recently and was interested how it could used for descriptive complexity theory.
Such link seems natural to me: you can give construction of algebraic model for formula as an ASM. ...
- 295
2
votes
1
answer
277
views
Deciding finiteness of regular language is NL-complete?
I've been reading the following Habilitation thesis where the author claims (pg. 29):
... First, deciding whether the language of an NFA is finite is in NL ...
I'm having trouble seeing why this ...
user70406
1
vote
0
answers
77
views
Conditional lower bounds for reachability
Are there conditional lower bounds for the deterministic time complexity of directed reachability algorithms? Maybe something linked to the Strong Exponential Time Hypothesis (SETH)?
I mean some ...
- 1,588
0
votes
0
answers
165
views
Decidability of the complexity of decision problems
This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to ...
- 101
0
votes
0
answers
114
views
Counterexample in Sistla and Clarke's paper
I'm reading Sistla and Clarke's paper "The Complexity of Propositional Linear Temporal Logics". In section 4 they start with the following set up:
Let $S=(s, \xi), T=(t, \pi)$ be structures ...
- 921
1
vote
1
answer
108
views
Complexity of analytic functions and integrals
There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this:
To which class do analytic elementary functions, including trigonometric ones, ...
- 13
5
votes
0
answers
125
views
Do fast satisfiability algorithms imply fast algorithms for parity SAT?
$\oplus$SAT is the problem of deciding if the number of satisfying assignments to a CNF formula is odd (and is the standard complete problem for the class $\oplus$P, or Parity-P).
Suppose we have a ...
- 3,416
7
votes
0
answers
104
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 ...
- 576
0
votes
0
answers
46
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
77
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.
...
- 900
1
vote
0
answers
84
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
2
votes
0
answers
57
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,588
3
votes
0
answers
103
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 ...
13
votes
1
answer
895
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 ...
- 7,465
1
vote
0
answers
39
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. ...
- 111
1
vote
1
answer
140
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 ...
- 183
9
votes
1
answer
328
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\...
- 619
3
votes
0
answers
162
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
1
vote
0
answers
99
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 ...
- 111
0
votes
0
answers
56
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.8k
0
votes
0
answers
67
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 ...
- 921
4
votes
1
answer
63
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 ...
- 7,465
6
votes
3
answers
328
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 ...
- 113
1
vote
1
answer
112
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 ...
- 31
1
vote
0
answers
84
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
6
votes
1
answer
342
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{...
- 958
1
vote
0
answers
72
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
78
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 ...
- 900
5
votes
1
answer
154
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,204
0
votes
1
answer
56
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_{...
- 1
3
votes
1
answer
173
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 ...
- 33
0
votes
1
answer
143
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 ...
1
vote
0
answers
124
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
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
123
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 ...
- 468
13
votes
2
answers
370
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 ...
- 131
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
2
votes
0
answers
71
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
0
answers
75
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, ...
- 1,588
4
votes
1
answer
69
views
Does there exist constant overhead reduction between common cryptographic primitives?
I have proved that there exist such reduction between error-correcting codes and exposure resilient functions, which is because that the transpose of a generator matrix for a ERC mapping $\mathbb{F}_2^...
1
vote
0
answers
71
views
Consequences of a $Parity$ $P$-problem being reducible to a sparse language?
$Parity$ $P$ is the class where an $NP$-machine answers $YES$ if and only if the number of accepting paths of that turing machine is odd.
With regards to the $P$ vs $NP$ question, there is a theorem ...
user69160
7
votes
2
answers
1k
views
Problems in NP with non-trivial certificate
For all NP-complete problems I can think about, the problem statement says very clearly how to test a certificate. I'm looking for interesting problems with NP which have non-trivial certificates. I ...
- 464