Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,143
questions
0
votes
1answer
43 views
Provide a polynomial time algorithm that decides whether or not the language recognized by some input DFA consists entirely of palindromes
Everything needed to know is in the question statement. I believe that the DFA has to be acyclic (meaning its language is finite), which can be checked in polynomial time. However, finding all paths ...
18
votes
4answers
3k views
How hard would it be to state P vs. NP in a proof assistant?
GJ Woeginger lists 116 invalid proofs of P vs. NP problem. Scott Aaronson published "Eight Signs A Claimed P≠NP Proof Is Wrong" to reduce hype each time someone attempts to settle P vs. NP. ...
0
votes
2answers
36 views
Complexity of Subset Sum where the size of the subset is specified
I know it should be easy but I'm trying to determine the complexity of the following variant of Subset Sum.
Given a subset $S$ of positive integers and integers $k>0$ and $N>0$, is there a ...
1
vote
1answer
41 views
Speedup with multi-head Turing Machine
What sort of speedup can a Turing machine with more than one head give vs a one-headed machine (I do not mean multiple tapes, I mean multiple heads operating on the same tape making concurrent edits ...
2
votes
0answers
35 views
How do you convert an NP problem which runs in O(f(x)) time in a SAT instance with O(f(x)*log(f(x))) variables in O(f(x)*log(f(x)))
I looked at the Cook's theorem at Wikipedia which presents a way to convert any NP problem to SAT but it seems to require O(f(x)^3) variables. Is it possible to remove some of the checks in the ...
-2
votes
0answers
45 views
Communication complexity
Alice enjoys watching table tennis and in her local league there are n players, each of whom is assigned an identification number between 1 and n.
Unfortunately Alice had to leave before the end of ...
1
vote
1answer
23 views
Relations between deciding languages and computing functions in advice machines
I'm trying to understand implications of translating between functions and languages for P/Poly complexity. I'm not sure whether the following all makes sense. Giving it my best shot given my current ...
0
votes
0answers
17 views
About the complexity of deciding if the closed world assumption for renamable Horn CNF is consistent
Let $T$ be a theory that only contains renamable horn formulas. What is the complexity of deciding if the closed world assumption $CWA(T)$ is consistent?
The closed world assumption is defined as ...
0
votes
2answers
67 views
If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?
I discover this in All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?
If problem B is in P and A reduces to B, then problem A is in P.
Problem B is NP-complete ...
2
votes
1answer
58 views
Counting circuits with constraints
Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).
In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be ...
2
votes
2answers
107 views
Is $EVEN-SAT$ $NP$-hard?
I'm looking for an $NP$-hardness proof for the following variant of $SAT$:
$$
EVEN-SAT = \{\langle \phi \rangle: \phi \text{ has an even number of satisfying assignments}\}
$$
I've been playing around ...
2
votes
1answer
73 views
Maximization problem on finite collection of finite sets
Problem
I am considering the following maximization problem:
Input is a finite collection of finite sets $\mathcal{F} = \{ X_1, X_2, \ldots, X_n \}$.
Goal is to find a subset $G \subseteq \mathcal{F}$...
3
votes
0answers
62 views
Is minimising the total number of one entries in binary matrices $CA$ and $C^TB$ NP-HARD?
Given a two rectangular binary matrices $A$ and $B$ with dimensions $c\times a$
and $c \times b$ respectively, does there exist an invertible binary
matrix C with dimensions $c \times c$ such that the ...
3
votes
1answer
112 views
How many clauses are required for SAT to be NP-hard in CNF formulas?
It is not hard to see that SAT for a CNF formula with $n$ variables and a constant number of clauses can be solved in polynomial time. On the other hand, it is not hard to see that a CNF formula with $...
1
vote
1answer
58 views
Is protein folding NP-hard and how to prove that?
This question has two facets that are related.
Is the general problem of protein folding really NP-hard?
The hydrophobic-polar protein folding model (Ken Dill et al., 1985) stated the problem on a ...
0
votes
0answers
22 views
$NP$ is not in $P(n^k)$ for any fixed $k \geq 1$
I encountered this problem which asks to show that for any fixed $k \geq 1$, $NP$ is not contained in $P(n^k)$...
As an attempt, I thought of using the time hierarchy theorem which says that there ...
0
votes
1answer
47 views
Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$
Given an alphabet, say $\Sigma = \{0,1\}$, I can make a one-to-one mapping from all possible strings $x \in \Sigma^*$ to $\mathbb{N}$. This could be done by ordering $\Sigma^*$ lexicographically and ...
0
votes
1answer
40 views
How are prime implicates of HORN-Formulas defined?
I'm confused about the definition of prime implicates in Horn formulas.
For example in the paper of Kira 2012 on page 109 it is stated:
Now in the paper of Boros 2010 on page 82 the following ...
1
vote
2answers
65 views
can it be said that NL^NL = NL?
I was wondering if it can be said that $\mbox{NL}^\mbox{NL}=\mbox{NL}$. That is, a decision problem $S$ can be decided using a nondeterministic TM using logarithmic space with oracle calls to $S'\in \...
-1
votes
2answers
66 views
I can verify solutions to my problem in polynomial time, how would a non-deterministic algorithm arrive to a solution if it always takes $2^n$ bits?
Decision Problem: Given integers as inputs for $K$ and $M$. Is the sum of $2^k$ + $M$ a $prime$?
Verifier
...
0
votes
1answer
30 views
Equivalence of Horn formulas tractable?
Assume I have two Horn formulas $\phi_1, \phi_2$. Horn formulas are CNF formulas so that each clause has at most one unnegated literal. For example:
$x_1 \wedge (\neg x_1 \vee \neg x_2 \vee x_3 )\...
5
votes
1answer
78 views
Conway's Game of Life: Is it really P-complete?
Wikipedia claims that the Game of Life is P-complete (or the decision problem version of it is; the function version, I suppose, would then be FP-complete).
Colloquially, P-complete and FP-complete ...
2
votes
2answers
69 views
Equivalence of Krom formulas tractable?
Assume I have two Krom formulas $\psi_1, \psi_2$. Krom formulas are propositional formulas in CNF that have 2 literals in every clause. Each literal can be negated or unnegated. In other words, $\...
1
vote
1answer
42 views
Why is this language Turing recognizable and not not-Turing recognizable
I read that the following language is r.e. but not not-Turing recognizable
$L$: On input $M$ (where $M$ is a Turing Machine), $M$ accepts at least 20 inputs
I am not sure why it is not not-Turing ...
0
votes
1answer
40 views
How to define enumeration of the set of finite state machines?
I want to write a function that takes N (maximum number of states) as a parameter, enumerates all possible finite state machines up to N states, and returns random FSM with a probability in proportion ...
2
votes
0answers
25 views
Reducing Dominant Set Problem to SAT
I am trying to solve a problem and I am really struggling, I would appreciate any help.
Given a graph $G$ and an integer $k$ , recognize whether $G$ contains dominating set $X$ with no more than $k$ ...
-2
votes
0answers
36 views
-3
votes
0answers
37 views
If A ∉ NP then A ∈ co-NP. True, false or we don't know?
If A ∉ NP then A ∈ co-NP.
True, false or we don't know?
0
votes
1answer
33 views
Worst Case for AVL Tree Balancing after Deletion
After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST).
The Balancing ...
0
votes
1answer
33 views
If A is polynomial-time reducible to B and B is NP-Complete, can I say that A is NP-Complete as well?
I searched a lot on internet, including here, but I couldn't find an explanation that could convince me. The problem is the same of the title, if A is polynomial-time reducible to B and B is NP-...
0
votes
1answer
19 views
What is the difference between SIZE(n^k) and P/poly?
What is the difference between $\text{SIZE}(n^k)$ and $\text{P}/\text{poly}$?
For reference:
$\text{SIZE}(n^k)$ is defined as the class of problems solvable with Boolean circuits (of fan-in two) with ...
1
vote
0answers
7 views
Lower bounds for orthogonal matrix multiplication
Is it possible, according to the current state of knowledge, that orthogonal matrices can be multiplied faster than arbitrary matrices?
More precisely, let $T(N)$ denote the worst-case time of the ...
0
votes
1answer
39 views
If X is polynomial-time reducible to Y and X is polynomial-time reducible to Z then Y is polynomial-time reducible to Z?
If $X$ is polynomial-time reducible to $Y$ and $X$ is polynomial-time reducible to $Z$,
$Y$ is polynomial-time reducible to $Z$?
If $X \leq_p Y$ and $X \leq_p Z$ then $Y \leq_p Z$?
True, false or we ...
-1
votes
1answer
34 views
If X is in NP then $\overline{X}$ is in NP. True, false or “we don't know”? Why?
If X is in NP then $\overline{X}$ is in NP.
True, false or "we don't know"? Why?
-3
votes
1answer
35 views
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
Is this true, false or "we don't know"? Why?
0
votes
0answers
26 views
Is finding the mean of the subset with the smallest variance NP-hard?
Let $x_1,\ldots, x_n \in R^d$, and $\alpha \in (0, 1)$. For simplicity, 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(\...
0
votes
0answers
13 views
Understanding definition of #P [migrated]
Valiant defined $\#P$ in terms of a counting TM, which is a NTM that outputs the number of solutions [1].
I am a bit stuck with the following two questions:
Let's say I have a decision problem $X$, ...
0
votes
1answer
25 views
Out-Degree of a Configuration Graph
In Chapter 4 in Computational Complexity by Arora and Barak it states, regarding the configuration graph of a Turing Machine, that
If M is deterministic, then the
graph has out-degree one, and if M ...
0
votes
0answers
24 views
Is $DSPACE(n^8) \subset NSPACE(n^5)$?
I encountered this problem which asks whether $DSPACE(n^8) \subset NSPACE(n^5)$ is sure to hold.
I know from Savitch's Theorem that:
$$
NSPACE(n^5) \subseteq DSPACE((n^5)^2)
= DSPACE(n^{10})$$
If the ...
0
votes
1answer
25 views
Is NSPACE(2^O(n)) = NSPACE(n^2 * 2^(O(n))
As said in the title, i am quite curious wether
NSPACE(2^(O(n)) equals NSPACE(n^2 * 2^(O(n))
I am aware of the fact, that NSPACE(k * 2^O(n)) equals NSPACE(2^O(n))
due to linear space reduction (i.e. ...
2
votes
1answer
14 views
Circuits and formulas for Clique
Is it correct to say that the Clique Problem is in $P$ iff there exists a family of Boolean circuits $C$ to decide Clique whose sizes are bounded by a polynomial? And based on this question, does that ...
1
vote
0answers
34 views
k-limited solution for PCP
So there's following problem, that has been bugging me for the last few days:
A solution of a PCP $ i_{1},\dots,i_{n}$ with the cards $(x_{1} ,y_{1}),\dots,(x_{m}, y_{m})$ is considered as $k$-...
0
votes
1answer
31 views
Complexity analysis of m!/n!(m-n)!
Given the runtime of an algorithm to be m!/(n!*(m-n)!) That is mCn, where both m and n are variables, is the complexity factorial or polynomial? Or is it something else?
Please elaborate.
Thanks
19
votes
8answers
4k views
Is Group Theory useful in Computer Science in areas other than cryptography?
I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
0
votes
1answer
37 views
Is my reasoning wrong that $PSPACE$ should not equal $EXPTIME$?
It's impossible for a problem to require exponential space without being exponential-time.
Consider that if an $EXPSPACE~~complete$ problem can be solved in $2^n$ time. It will now fall into the ...
1
vote
0answers
15 views
Configurations and CNF formula for neighboring configuration
A configuration of a Turing machine $M$ which runs in space $S(n)$ contains the state, the head positions, and the content of non-blank cells of all the tapes. For $M$ and an input $x$, we define its ...
7
votes
1answer
239 views
Is the buckets of water problem in NP?
Continuing from this question: the buckets of water problem.
(All the definitions can be found there, so I will not repeat them).
As seen there by Yuval's answer, the problem is NP-Hard.
I was ...
9
votes
7answers
4k views
Checking equality of integers: O(1) in C but O(log n) in Python 3?
Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are $O(1)$.
def is_equal(a: int, b: int) -> bool:
return a == b
<...
1
vote
1answer
34 views
Arthur-Merlin protocol
I recently learned about the Arthur-Merlin protocol, and we defined the complexity classes $AM,MA$.
We have also seen that there exists a theorem stating that $AMAMAM...AM=AM$, however we have not ...
1
vote
1answer
42 views
TSP 200-approximation, given $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ for all nodes $x,y,z$
Input: complete, undirected graph $G=(V,E)$ and cost function $c$
Assume for all nodes $x,y,z \in V$: $c(x,z)\le c(x,y) + 100\cdot c(y,z)$
Find a 200-approximation polynomial time algorithm for the ...
