Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
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

If B ∈ NP and A <= B then A ∉ EXP?

If B ∈ NP and A <= B then A ∉ EXP. True, false or we don't know?
-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 ...

1
2 3 4 5
83