All Questions
Tagged with complexity or complexity-theory
5,612 questions
2
votes
0
answers
28
views
I know the following language is undecidable by reduction to HP bar. But how does it relate to L_EQ?
The languages are defined as such (for standard Turing machines and over $\{0, 1\}^*$:
$$
L_3 \triangleq \{
(\langle M \rangle, x) \mid \text{$\forall M^\prime, [x\in L(M^\prime)] \lor [\langle M^\...
- 21
0
votes
1
answer
91
views
Why $TIME(2^{n^k})\nsubseteq NTIME(n^k)$?
There is a theorem that said for every nondeterministic Turing machine that runs in $O(n^k)$ there is an equivalent deterministic Turing machine that runs in $O(2^{n^k})$.
From this theorem, I ...
- 191
1
vote
1
answer
84
views
Does log(log(n)) grow asymptotically slower than log(n) / log(log(n))?
I'm trying to understand the asymptotic growth of relationship between log(log(n)) and log(n) / log(log(n)) as n -> infinity.
Specifically, I want to verify whether this statement is true or false:
...
- 13
2
votes
1
answer
79
views
A problem that is NP-complete on m by n grids
Is there any problem out there that is known to be NP-complete on the m by n grids?
I know domination is proved to be NP-complete even on the grids, but not on the m by n grids.
A grid graph in ...
1
vote
1
answer
45
views
Is P/poly is contained in NP?
I learned that $\textsf{P/poly}$ is a class of problems computable by a polynomial-size circuit.
This class is considered a class of problems such that there exists a polynomial-time algorithm that is ...
0
votes
1
answer
61
views
need to prove that $DSPACE(O(2^n)) \neq EXP$
this question is from my computational complexity HW.
I'm not sure if my solution is correct:
If $DSPACE(O(2^n)) = EXP$, than we can take language $ L \in DTIME(2^{2^n})$ which not in $EXP$ (from the ...
0
votes
2
answers
68
views
Graph contains two disjoint cliques
Is $$\text{2disjCLIQUEs} =
\left\{ \langle G, k_1, k_2 \rangle : \text{ the graph $G$ contains two disjoint cliques,one of size $k_1$, and the other of size $k_2$}\right\}$$ in $\texttt{P}$ or $\...
- 25
1
vote
1
answer
45
views
Given $4$-coloring decide $3$-colorability in $P$?
Input: a valid $4$ coloring of graph $G$
output: accept iff $G$ is $3$ colorable
Can this be done in polynomial time ?
I cannot reduce $3$ coloring to this problem (this requires us to find a $4$ ...
- 171
1
vote
1
answer
69
views
$\textbf{NP}\neq \textbf{DTIME}(2^{\sqrt{n}})$
I want to prove that $\textbf{NP}\neq \textbf{DTIME}(2^{\sqrt{n}}).$
My thoughts is:
if I try to prove $\textbf{NP}\not\subseteq \textbf{DTIME}(2^{\sqrt{n}})$ would imply $\textbf{NP $\neq$ P}$.
if ...
- 25
0
votes
1
answer
73
views
Proving TWO-COLORED-HAMILTONIAN-CYCLE is complete
Consider the following problems:
TCHC :=
{
⟨G, c⟩ | G(V, E) is a directed graph with an even number of vertices along with
an edge coloring c and G has a directed Hamiltonian cycle with no
two ...
- 3
2
votes
1
answer
54
views
NP reducibility proof steps
Can someone help me to verify my understanding of reducible NP problems?
Look at this tree:
The root shows the most complex NP complete problem. So, given that circuit-sat is NP complete, by this ...
- 109
0
votes
0
answers
25
views
Computational complexity of “Linear divisibility” problem (Adleman & Manders 1972)
[Information/resource request]
Linear Divisibility:
In the study of $\gamma$-reduction that generalizes Karp reduction, Adleman and Manders [1972] mentioned the following language:
$$A = \{\langle a,c\...
- 163
1
vote
0
answers
25
views
What happens when the number of coin-flips are restricted in probabilistic Turing machines
If all probabilistic Turing machines make at most $\mathcal{O}(\log n)$
number of coin-flips before termination when run on an input of length n , or such machines can always be constructed for ...
- 11
1
vote
1
answer
55
views
$SET-COVER\leq_pIP$
Let:
$IP=\left \{ \left \langle A,b \right \rangle \right \}:$ $A$ is a $m\times l$ matrix over the integers, $b$ is a vector of $m$ integers and there exists a vector $x$ of $l$ integers s.t $Ax\geq ...
- 191
0
votes
1
answer
45
views
Why does nondeterministically estimating a number have exponential time complexity?
One way to determine whether a number is prime is to try all possible
integers less than that number and see whether any are divisors, also
called factors. That algorithm has exponential time ...
- 11
0
votes
1
answer
51
views
Can't we model a probabilistic turing machine using deterministic turing machine?
I was trying to get my head around turing machine and I have such question.
Let's take a deterministic turing machine.
We know it has a transition function.
Now can't this transition function have ...
- 1
0
votes
1
answer
62
views
Prove in place acceptance is $PSPACE$-complete
I want to prove that the language $IN-PLACE-ACCEPTANCE$, abbreviated as $IPA$, is $PSPACE$-complete. The language is defined as $\{<M,x> | M(x) = 1, M\ doesn't\ use\ any\ extra\ space \}$. Not ...
- 7
0
votes
1
answer
65
views
Two definitions of coNP
If $L\subseteq \{0, 1\}^∗$ is a language, then we denote by $\overline{L}$ the complement of $L$. That is, $\overline{L} = \{0, 1\}^∗\setminus L.$
We make the following one definition of $\mathrm{...
- 23
0
votes
0
answers
54
views
Whether $\text{TQBF}\in\mathbf{PH}$ by a set theory inference
Let $L_i\subseteq\text{TQBF}$ be the set of true $i$-run PNF quantified boolean formulas, e.g. $\exists x\;\forall y\;\exists z\;((x\land z)\lor y)\in L_3$. As a result, we have $\text{TQBF}=\bigcup_{...
- 521
0
votes
1
answer
77
views
Show that $PH\subseteq EXP$
The question is "Show that $PH\subseteq EXP$. In other words, show that any language $L\in PH$ can be decided in time $2^{O(n^c)}$ for some constant $c$. The PH here is referring to polynomial ...
- 7
0
votes
0
answers
59
views
Is either $\mathsf{BPP}$ or $\mathsf{NP}$ low for the other? And $\mathsf{PP}$ vs. $\mathsf{NP}$?
Is it an open question whether $\mathsf{BPP}$ is low for $\mathsf{NP}$?
Is it an open question whether $\mathsf{NP}$ is low for $\mathsf{BPP}$?
If both are open questions, what do you think is more ...
- 192
0
votes
1
answer
35
views
Proving equivalence of an alternative definition for $BPP$ class
I want to prove that the following definition also defines $BPP$ and is equivalent to the standard definition:
A language $L$ is in $BPP$ if there's a polynomial time Probabilistic Turing Machine $M$, ...
- 7
0
votes
0
answers
18
views
Are complexity classes non-monotonic ("dense")?
I am wondering if the following property is true: given any two deterministic time complexity classes $\textsf{DTIME}(f(n))$ and $\textsf{DTIME}(g(n))$, such that $\textsf{DTIME}(f(n)) \subsetneq \...
- 291
0
votes
0
answers
151
views
What's wrong with the proposed semidefinite programming (SDP) formulation for approximating the Vertex Cover Problem (VCP)?
I have proposed an approximation algorithm for VCP that may produce a less than 2 approximation ratio.
I know this contradicts what experts believe about the Unique Games Conjecture. However, I was ...
0
votes
0
answers
18
views
Are there an infinite number of distinguishable time complexity classes contained in any given class?
Let $f:\mathbb{N}\rightarrow \mathbb{N}$ be a monotone increasing function. Then, do there exist an infinite number of complexity classes below $\textsf{DTIME}(f(n))$? That is, do we have an ...
- 291
0
votes
1
answer
28
views
Is $\operatorname{ECLIQUE}$ in $\Pi_2^p$?
I was watching this lecture on the Polynomial hierarchy and one of the presented examples was the language \begin{equation*}
\operatorname{ECLIQUE} = \{ \langle G, k \rangle \; : \; G \text{ is a ...
- 85
0
votes
0
answers
7
views
Is there a name for the complexity class for an oracle for matrix elements of arbitrary polynomial-size unitary circuits?
Suppose you had an oracle that could efficiently compute matrix elements (in the computational basis) $\langle x | C | y \rangle$ for arbitrary polynomial-size circuits $C$. Is there a name for the ...
- 1,146
0
votes
0
answers
52
views
Are there any nice examples of problems in E / NE?
Let $E = DTIME(2^{O(n)})$ and $NE = NTIME(2^{O(n)})$ be the deterministic/nondeterministic complexity classes of problems decidable in exponential time with linear exponent.
There are many examples of ...
1
vote
0
answers
26
views
Special case of rank minimization
The problem takes as input an $m \times 2n$ matrix $A$ over $\mathbb{F}_2$.
Optimization version: find a subset of exactly $n$ columns so that the corresponding submatrix (taking only selected columns)...
1
vote
1
answer
99
views
Is it NP-hard to decide whether a graph is balanced bipartite?
The problem is the following. On input, an undirected graph $G = (V, E)$. Question: can $V$ be partitioned into two (disjoint) subsets $V = V_1 \cup V_2$, with $-1 \leq |V_1| - |V_2| \leq 1$ so that ...
1
vote
1
answer
110
views
Whether $\textbf{PH}$ collapses to $\Sigma^p_1$ when $\overline{3SAT}\in \textbf{BP$\cdot$NP}$
I'm doing ex. 7.8 in Arora and Barak
Show that if $\overline{3SAT}\in \textbf{BP$\cdot$NP}$, then $\textbf{PH}$ collapses to $\Sigma_3^p$.
This is definition of $\textbf{NP}/poly$:
A ...
- 521
0
votes
1
answer
135
views
$L\in P\to L^*\in P$ and the delicate of induction
The question asks to prove that if $L\in P$ then $L^*\in P$.
What I wrote
Notice that $L^*=\bigcup_{k\in\mathbb{N}}L^k$.
We use induction in order to prove the claim:
Base:
For $L^2$ we can construct ...
- 191
0
votes
1
answer
31
views
Is it possible to convert a Boolean Formula to "negative normal form" in polynomial time?
A Boolean formula using only negation $\neg$, AND $\land$ and OR $\lor$ is said
to be in negative normal form if the negation only appears in front of a variable, like this $\neg(x)$.
So for instance, ...
0
votes
1
answer
61
views
Can I transform any given boolean expression to conjunctive normal form to solve SAT?
I am confused about the hardness of SAT(Boolean Satisfiability Problem). It takes polynomial time to transform any given boolean formula $f$ to a conjunctive normal form. I mean polynomial in the ...
- 3
0
votes
0
answers
54
views
Sufficient condition for simulation of $A^{B}$ by $C$
The task is to show $A^{B}\subseteq C$, where, $A,\ B$ and $C$ are complexity classes.
Is (i) $A\subseteq C$, (ii) $B\subseteq C$ and, (iii) $B$=co-$B$ are sufficient conditions to deduce $A^{B}\...
- 163
0
votes
1
answer
46
views
Ways to prove a problem is hard for a class
If I want to prove that some language $A$ is hard for class $C$, the obvious way is a Karp reduction. You could also show it by finding some subset of $A$ that's hard for $C$.
What other ways are ...
2
votes
1
answer
76
views
Complexity of identifying "generic & distinguishable" Moore machines
Consider a non-deterministic Moore machine with input alphabet
$\Sigma
\newcommand\OO{\mathcal{O}}
\newcommand\o{\mathfrak{o}}
\newcommand\PP{\mathcal{P}}$ and output alphabet $\OO$, a set of states $...
- 31
1
vote
2
answers
61
views
Calculating complexity for recursive functions with substitution method (Big O notation)
(https://i.sstatic.net/oTCBO87A.png)
I have to calculate the complexity of this algorithm using the substitution method but I don't understand how to do it.
I'm guessing that ...
- 11
0
votes
0
answers
21
views
LP duality for approximate bounded degree
$\begin{align*}
&\text{min } \epsilon \\
&|f(x) - \sum_{|S|\leq d} c_S \chi_S(x)| \leq \epsilon, \ \ \ x \in D \\
&|\sum_{|S| \leq d} c_S \chi_S(x)| \leq 1 + \epsilon, \ \ \ x \in \{-1,...
1
vote
0
answers
98
views
Are Prof. Arora and Barak maintaining Computation Complexity: A Modern Approach?
Does the book Computation Complexity: A Modern Approach have an official errata page like Knuth's books and CLRS, maintaining by their authors? I have tried to find its comprehensive errata page to ...
- 521
0
votes
1
answer
112
views
Is $\text{logCLIQUE}\in \texttt{NSPACE($\log^2(n)$)}$?
I inspired by this question, $$\text{logCLIQUE}=\{\langle G\rangle:\text{G=(V,E) contains a clique of size $\log(|V|)$}\}.$$
Here $G$ is an undirected graph and it can be assumed that the number of ...
- 23
1
vote
0
answers
21
views
What is the distribution of the time complexity for the randomized selection (Quickselect) algorithm?
I'm studying the randomized selection algorithm, also known as Quickselect, which is used to find the k-th smallest element in an unordered list. The algorithm can be defined as follows:
...
- 131
1
vote
1
answer
32
views
Does an oracle of EXPSPACE-complete $B$ language cause $P^B=EXP^B$
As I have read Sipser's TOC, on page 372, there is a $EXPSPACE$-complete language, say, $B$, i.e. $B\in$ $EXPSPACE$ and every $L\in$ $EXPSPACE$ is polynomial time reducible to $B$.
I also have read ...
- 521
1
vote
1
answer
36
views
Types of Time Inconstructible Functions
So Wikipedia gives me notions of time and space constructibility and as far as I can tell, the two general definitions used are:
Functions $f: \mathbb{N} \to \mathbb{N}$ such that for all $n \geq n_0 \...
- 1,647
-1
votes
1
answer
54
views
Is this an algorithm that is theoretically polynomial, but practically exponential?
To solve a problem I have an algorithm $T(n)$ where,
the input of $n$ variables is transformed into $n$ numbers of size $>2^n!$,
then the algorithm requires $k.n^4$ arithmetic operations, where $k$...
- 23
2
votes
2
answers
105
views
Attempt to find a real number whose computation of bits is NP-complete
Recall that every real number $x$ can be expressed as $b + m$, where $b \in \mathbb{Z}$ is the integral part and where $m \in [0,1)$ is the mantissa.
Definition. A real number $x$ is said to be in a ...
- 387
0
votes
2
answers
58
views
How can one say solving one np-complete problem in polynomial proves that all np-complete problems can be solved in p?
I keep reading that we don’t know if p=np or if p!=np , but what is the basis for this universality?
This question is derived from this statement from the book Introduction to algorithms, third ...
- 1
0
votes
1
answer
25
views
Time Complexity of Backtracking solution to Leetcode 473. Matchsticks to Square
The following is a Leetcode problem: 473. Matchsticks to Square (https://leetcode.com/problems/matchsticks-to-square/description/)
Problem Statement
You have an array, matchsticks, of size n, with ...
- 1
0
votes
0
answers
25
views
if P≠NP then does P ≠ coNP?
If P ≠ NP then does P ≠ coNP?
If so please explain why?
I have tried thinking about subsets between langauges, but not sure where to start.
1
vote
1
answer
48
views
How to separate $TIME(n)$ and $L$?
I'm trying to prove that $TIME(n)\neq L$ by padding technique, yet it has a trouble:
Assume that $TIME(n)= L$, let $A\in TIME(n^2)\backslash TIME(n)$ so $A\notin L$. Let $A_{pad}=\{x01^{|x|^2-|x|-1}|x\...
- 521