Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,528
questions
0
votes
1answer
39 views
Counting strongly connected components in a directed graph in $NL$
Define $K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least $k$ strongly connected components} \}$
I want to show that $K\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}...
1
vote
1answer
32 views
Is it true that PRIMES are in SPARSE?
I'm wondering if PRIMES, the language of all prime numbers represented in binary, which is $\{10, 11, 101, 111, 1011, 1101, ...\}$, belongs to the SPARSE class, a set of all sparse languages, that is, ...
3
votes
2answers
276 views
Should the certificate for NPSPACE be polynomial in size?
There is a problem that I am working on. I have shown that the problem is NP Hard, but I haven't been able to show that it is in NP. But the problem is also known to be in EXP. My gut feeling is that ...
4
votes
2answers
27 views
How do you express a floor / ceiling in the approximation factor of an approximation algorithm?
Intuitively I feel like this is a bit of a dumb question, and is probably related to my vague understanding of approximation algorithms and whatnot.
Suppose I have some minimisation problem $X$ where, ...
0
votes
0answers
23 views
Why do exact MaxSAT algorithms scale exponentially as a function of the number of clauses?
As stated in this recent paper from ijcai https://www.ijcai.org/Proceedings/2019/0166.pdf
The top -Exact- algorithms worst case complexities are stated as follows
where m is the number of clauses in ...
0
votes
1answer
22 views
Question about reduction Proof
I've recently seen a proof that the set of Turing machines $L = \{encode(M) |L(M) \text{is closed under reversal}\}$ is not decidable.
The proof used following idea:
Reduce from the $A_{TM}$ problem ...
2
votes
0answers
26 views
How far would complexity hierarchies collapse if $L\in CoNP$ is $L\in NPH$?
Let $L\in CoNP$. Assuming that $L\in NPH$, what would we get?
So, as $L\in NPH$ then every language $A\in NP$ has a reduction $A \leq L$. This would mean that $\overline{L} \leq L$ as well. By ...
-1
votes
1answer
50 views
Does ⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛)
⌊1/𝑛⌋ - represents the floor function Does the floor or ceiling function affect the complexity under which a function falls?
⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛)
Found ...
1
vote
2answers
42 views
Prove that { $\langle M \rangle$ : $M$ is a TM and $L(M)$ is decidable} is undecidable
So I want to prove that $$ \big\{\langle M \rangle : \text{ M is a TM and } L(M) \text{ is decidable} \big\}$$ is undecidable.
To do so I want to reduce it from$\ \overline{A_{TM}}$ with a function ...
1
vote
3answers
83 views
1
vote
0answers
30 views
What computational hardness concept corresponds to strongly-polynomial time algorithms?
Consider the computational problems in which the input is a set of $n$ integers with maximum magnitude $M$. According to Erik Demaine's lecture notes, assuming $P\neq NP$, the following are true:
If ...
2
votes
1answer
34 views
Does $NP^{SAT}=NP^{NP}$?
Does $NP^{SAT}=NP^{NP}$?
We can see easily that $NP^{SAT}\subseteq NP^{NP}$, because $SAT \in NP$.
But is the other side $NP^{NP}\subseteq NP^{SAT}$ also true? If yes, how can we prove it?
1
vote
2answers
762 views
Why are all regular languages in P?
Just to be clear, I am aware that you can define an accepting DFA for every regular language. My problem is a bit deeper.
Let's say we have a language L which consists of a random half of all binary ...
1
vote
1answer
40 views
What is the comparator circuit?
The standard circuits $AC^i$, $NC^i$ are constructed using $AND$, $OR$ and $NOT$ of various fan-ins, fan-outs and depths.
What is the comparator gate constituted from?
Structurally why is it believed $...
0
votes
0answers
17 views
What is the depth of comparator circuit required in Gale Shapely and STCONN?
Stable matching problem and $STCONN$ can be solved using comparator circuits (refer https://arxiv.org/abs/1208.2721).
What is the depth of the $CC$ circuit necessary for stable matching? Is it in $CC^...
2
votes
0answers
26 views
Comparing PRAM and Circuit Complexity, $NC^i$
I wondered about the following quote from NC (Wikipedia):
$NC^i$ is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates of at most two inputs and ...
1
vote
1answer
32 views
Inapproximability of graph problems on a restricted setting
I am considering the following problem $\mathcal{P}$.
$\mathcal{P}$: Given an undirected graph $G$, and an integer $k$, find a set of vertices $S \subseteq V(G)$, with $|S| = k$, such that the number ...
0
votes
1answer
21 views
What is the relations between $\mathsf{DTIME}(2^{O(n)})$ and $\mathsf{DTIME}(n^{O(\log n)})$
What is the relations between $\mathsf{DTIME}(2^{O(n)})$ and $\mathsf{DTIME}(n^{O(\log n)})$? Is one contained in the other?
2
votes
1answer
46 views
Must all NP-complete problems have an asymptotically optimal algorithm?
According to Blum's speedup theorem, there exist problems with no asymptotically optimal algorithm. Suppose that NP-complete problems had speedup. We know a problem X with asymptotically time ...
3
votes
0answers
75 views
Remove a subsequence from a string and append it at the end
Consider the following operation on strings: pick a (not necessarily contiguous) subsequence, remove it and then append all the characters in the same order at the end. This operation preserves the ...
1
vote
1answer
25 views
Is there CIRCUIT-SAT algorithms that slightly depends on gates count?
For 3CNF-SAT problems exists a lot of algorithms that still have exponential complexity, but work faster than brute force. The complexity of this algorithm based on a number of variables or the number ...
1
vote
1answer
22 views
If $S\in\left(NP\bigcup coNP\right)$ then $\overline{S}\in NP\bigcap coNP$?
Is it true that if $S\in\left(NP\bigcup coNP\right)$ then $\overline{S}\in NP\bigcap coNP$?
I couldn't find any answer to that question.
My attempt at proving it:
If $S\in\left(NP\bigcup coNP\right)$, ...
1
vote
1answer
30 views
If $NP \neq coNP$ then $BPP \neq NP$
I am new in complexity theory and I am trying as part of an assignment to prove or disprove this.
I am thinking this is a true statement but I am not sure how to prove or disprove it or what the ...
0
votes
0answers
25 views
What do HC and HL (hamiltonian graph problems) stand for?
Hopefully, this question is fine.
I'm referring to the NP-complete problems regarding hamiltonian graphs.
I suppose the C in HC is from Cycle or Circuit. It seems like Circuit is more popular.
HL (...
1
vote
1answer
55 views
Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
Let $C$ be an uniform complexity class for example $NL$ or $NP$. Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
3
votes
0answers
53 views
How to replace the max distance of a bounded set of points with a random point in less than $O(n^2)$?
Context
Let's say I have a finite set of points of size $N$.
I can represent the points in a metric space and then compute distances between them.
My goal is to replace a point in the set with another ...
0
votes
1answer
64 views
Assume P != NP, are these assertions valid?
Assume $P \ne NP$, and $A$ is a problem in $P$ and $B$ is a problem which is $NP-complete$.
Are the following assertions valid?
$A \le_{P} B$
$B \le_{P} A$
My approach:
$B \le_{P} A$ isn't valid, ...
1
vote
1answer
43 views
Accounting method - dynamic array
I want to compute the amortize time of a type of dynamic array (inserting such that if i have no place to insert i am multipling the array by (1+a) (a is between 0 to 1).
I need to compute the time ...
-1
votes
1answer
40 views
Are the following assertions true if P != NP?
We consider the NP-complete $CLIQUE$ problem. Let furthermore $MST^*$ be the minimum spanning tree problem. Assume that $P \ne NP$ and explain whether the following assertions hold:
$MST^* \le_{P} ...
2
votes
1answer
42 views
Is quadratic nonresiduosity in $\textbf{NP}$?
The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an ...
0
votes
1answer
57 views
Finding an Algorithm for the HAPPY-CAT problem
I'm trying to develop an the algorithm for the problem:
The cat-and-mouse game is played by two players, “Cat” and “Mouse,” on an arbitrary undirected graph. At a given point, each player occupies a ...
0
votes
2answers
90 views
How to reduce the hamiltonian path problem to 1/2 hamiltonian path problem
Task:
A Hamiltonian path of a graph is a path that visits all nodes of the graph exactly once. The hamiltion path problem (HPP) consists in deciding whether a given graph has such a path. Similarly, ...
-1
votes
0answers
16 views
ist the certificate and the verifier appropriate to show that the problem is in NP?
Consider whether the certificate and the verifier are appropriate to show that the given problem is in NP.
Given problem: Given is a formula $\Phi$ in conjunctive normal form. Is the formula ...
3
votes
1answer
37 views
Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?
Suppose there is graph problem $L$ such that the instance $x$ of $L$ is a simple graph with $n$ vertices and $m$ edges.
In the Turing machine model, we can encode a graph using $O(n^2)$ cells or $O((m+...
2
votes
1answer
88 views
Prove that any algorithm that has sublinear time have a constant time complexity?
This exercise is taken from Goldreich's textbook of "Computational Complexity - A Conceptual Perspective", first ed., p.140.
Exercise 4.3: Referring to any reasonable model of computation ...
2
votes
1answer
64 views
$\epsilon$-approximation Sub-linear time monotonicity testing
I have the following exercise I have been staring at for several hours to no avail.
Question:
Testing the monotonicity of a function - the case of bits: Given a function $f: [n] \rightarrow \{0,1\}$ ...
0
votes
2answers
39 views
Is every problem with an output's size that grows polynomialy np?
I am wondering if every problem with an output's size that grows polynomialy is $\textsf{NP}$?
My thinking is every $\textsf{NP}$ problems can be solved in polynomial time by a non-deterministic ...
1
vote
1answer
24 views
Slowdown in making nondeterministic Turing machines deterministic
For every nondeterministic Turing machine, must there exist an equivalent deterministic one that runs in no more than twice the time?
Why or why not?
Can anyone explain?
1
vote
1answer
18 views
Is there a mapping reduction for every two language $A$ and $B$ to some language $C$?
One of my friend told me that there is a language $C$ for every two languages $A$ and $B$ s.t $A \leq_{m} C$ and $B \leq_{m} C$ , he simply define two languages $A’=\{0w|w \in A\}$ and $B’=\{1w|w \in ...
0
votes
0answers
21 views
Cost of solving linear equation using FFT algorithm
I have a linear equation $Cx=b$ where $C$ is $n \times n$ circulant matrix. By applying circular convolution process, vector $x$ can be solved using Fast Fourier Transform (FFT) to transform the ...
1
vote
1answer
61 views
Proof plan for P ≠ NP
Let $M$ be a Turing Machine for SAT. We want to encode certain paths of $M$ in a very short way in order to diagonalize against the paths.
For each natural number $k$, we will have a formula $\phi$ of ...
1
vote
0answers
25 views
How do we know that this Karp-Lipton theorem is derived from relativizing arguments?
Luca Trevisan wrote, " The oracle $C$ tells us that we cannot have a relativizing proof that derives the $𝑁𝑃 ⊈ 𝑃/𝑝𝑜𝑙𝑦$ conclusion from the $𝑃 ≠𝑁𝑃$ assumption, so a theorem such as Karp-...
1
vote
0answers
30 views
Prove that characteristic function $f_w$ in write protected input turing machine behave as a 2FSA
Write protected input turing machine is a single-tape TM that cannot write on the input portion of the tape. I almost prove that these TMs can only recognize regular languages but i have a problem in ...
1
vote
1answer
17 views
Is it possible to have a zero knowledge proof with a P Prover?
In the literature, when reading about zero knowledge proofs, the prover (prover/verifier) is always given an unlimited computational power or just capacity to solve NP.
Is it necessary for the prover ...
-3
votes
0answers
27 views
Set of CNFs with at least two satisfying assignments belongs to NP [duplicate]
Let DOUBLE-SAT = { ⟨φ⟩ | φ has at least two satisfying assignments }. Show that DOUBLE-SAT is in NP by giving a polynomial-time verifier for it and describing why the verifier runs in polynomial time.
1
vote
1answer
23 views
How to prove that the reduction relation is not symmetric
I know that the reduction relation is not symmetric. Writing formal proofs is the main core of the course I take on Theory of Computation. So I'm trying to prove that theorem. For that I need to show ...
3
votes
1answer
30 views
Has it been shown or can we show that if $SAT \in P$ then SAT can't be in any complexity class C so that $C \subsetneq P$?
I'm already guessing that the answer is no because we cannot know whether there is a class "in between" already known classes? Or can we?
I am very new to complexity theory.
Thanks for any ...
0
votes
0answers
15 views
Time complexity of calculating the eigenvalues and eigenvector of a matrix
I know the time complexity of calculating the determinant of a square matrix of order $n$ is $O(n^3)$ (by using standard matrix multiplication). What is the time complexity of calculating the ...
1
vote
1answer
33 views
How to prove NP-hardness of a Hamiltonian Path problem by reducing longest-path problem?
I know how to prove longest-path problem by reducing Hamiltonian Path problem.
Here I want to prove NP-hardness of a Hamiltonion Path problem by reducing longest-path problem. (pretend we know longest-...
0
votes
1answer
27 views
Having trouble understanding blatantly non-private definition because of Little-o notation
I was pretty confident that I understand asymptotic notation until now. However, I am having a hard time understanding some basic definition that use asymptotic notation, specially little-o.
...
