New answers tagged complexity-theory
1
In order to show that $L_1 \leq L_2$, we need to come up with a computable function $f$ such that $x \in L_1$ iff $f(x) \in L_2$. Since $L_1 = \Sigma^*$, every $x$ satisfies $x \in L$, and so we need to find a computable function $f$ such that $f(x) \in L_2$ for all $x$. The easiest way to satisfy this is to choose $f$ to be a constant function.
In order to ...
2
SAT is NP-hard with respect to NC$^0$ reductions, and in particular, it is P-hard with respect to NC$^0$ reductions.
Now let $C$ be a complexity class which is closed under NC$^0$ reductions. If SAT is in $C$ then every problem in P can be reduced to $C$ using NC$^0$ reductions, and so belongs to $C$, implying that $C$ contains P.
3
Suppose you have a graph $G$ of order $n$. $G$ has a simple path of length $\geq n - 1$ if and only if $G$ has a hamiltonian path.
1
The interpretation of your professor is "intuitively correct" (but still formally wrong).
The notation $o(n)$ denotes the set of functions that grow less than linearly with $n$.
That definition means that, if we look at databases $d$ whose number of entries $n$ grows towards infinity, the candidate database $c$ will agree with $d$ in all but a ...
3
If you want to write $N$ words of output, it takes at least $N$ steps of computation to do that. So, if you need to produce an exponential-sized output, you'll need to spend exponential time to do it. For that reason, a polynomial-time reduction cannot produce an exponential-sized output when run on a polynomial-sized input.
2
The fact that the given reduction takes exponential space implies it must take exponential time and therefore is not polynomial.
Using Cook-Levin on a NP-complete problem does not produce an exponential-sized output; it produces a polynomial-time circuit. It constructs a circuit whose size is polynomial in the number of steps taken by the NP-verifier; since ...
1
The subset sum problem is quite different from your problem: Given a list of integers and a target sum $S$, it asks if there is a subset of the list that sums to $S$. No "compression", lossy or not. Any lossy technique will (by definition) tend to miss the target (because it works with an approximation). And we are looking for an exact solution, ...
2
No. Your argument is not valid; it doesn't prove NP-completeness. You have shown that an ILP solver can be used to solve your problem. But an ILP solver can be used to solve easy problems, too, so it doesn't rule out the possibility that your problem might be easy (solvable in polynomial time). The reduction needs to go the other way. I suggest studying ...
3
I am by no means an expert, but 2 things come to mind:
Because if we know things like $A^L \neq B^L$, for some $L$, then a proof of $A = B$ need to be non-relativizing. This puts constrains on the techniques used for such a proof, and thus it is helpful in the way towards getting a proof.
Because if you prove $A^L = B^L$, and the oracle is not very strong, ...
1
This was an examination paper question for Computability and Complexity, as the deadline has now passed, I am able to answer:
The basic answer to this is that it is quite literally, base 2, 3 and base 6.
If my answer itself was correct, you can see in the table we must have the second half of the answer to contain only "3" values, that is to say, ...
1
Your analysis seems correct, except for that you need $T(n)=T(index)+T(n-index+1)+2n$ instead because when $index$ is either $0$ or $n-1$ you won't get in the right hand side another factor of $T(n)$, which is not allowed.
In fact, it will yield something very close to the recurrence of the running time in the quicksort algorithm.
Worst case scenario
When ...
2
Hint. Whether or not a word $u$ belongs to your language only depends on the parity of two parameters: $x(u) = |u|_0 + |u|_1$ and $y(u) = |u|_1 + |u|_2$. Computing modulo $2$, this gives you four states, $(0, 0), (0,1), (1,0), (1,1)$. It remains to find the transitions. For this, you just have to compute $x(uc)$ and $y(uc)$ for each letter $c \in \{0, 1, 2\}$...
0
Since any input x for L can be reduced to SAT in O(|x|^c) time, the created SAT instance will have size at most n=O(|x|^c). So the n^(lg n)-time algorithm for SAT will be an |x|^O(lg |x|)-time algorithm for L.
0
You can easily define NP-hard optimisation problems: We call a decision problem D NP-hard if any decision problem in NP can be reduced to D in polynomial time. And we can use the same definition for any problem P: P is NP-hard if any decision problem in NP can be reduced to P in polynomial time.
The problem is defining something analogous to NP. If we have a ...
1
Just extending a bit more what Yuval Filmus has already said. Suppose your input is $x_1\ldots x_n$.
Let's use a memorization array $A$, where $A[i]$ is $True$ in case $x_1 \ldots x_i$ is in $L^*$ and is $False$ otherwise.
Consider the deterministic Turing machine $M$ that does the following:
Set $A[0]$ to $True$, since the empty string $\epsilon$ is in $L^*...
0
You need to look at every individual optimisation problem. Typically you want a “solution” which maximises the value v, while a decision problem would be “is there a solution with a value >= k”
The question is: if you can solve the decision problem, repeatedly, does that allow you to solve the optimisation problem? Usually it lets you solve “what is the ...
0
For the relation between decision and optimization (search) problems, take a peek at Bellare and Goldwasser's The Complexity of Decision versus Search, SIAM Journal of Computing 23(1), feb 1994. In a nutshell: If the decision problem is NP-complete, the search problem is hard too, and can be solved calling the decision problem's solver a polynomial number of ...
3
In general, if you know nothing about the array, then searching linearly is the best you can do (a simple adversarial argument is enough to justify this).
However, if you know more about the structure of the array, there are plenty of things you can do.
For example, imagine the array has the following property: its elements are sorted increasingly up to a ...
2
The other answers are correct, but f I may add an observation: it seems like you are conflating classes of problems and particular instances. There are a number of instances that can be solved in polynomial time in classes that are NP-hard in general. For instance, Boolean satisfiability is NP-hard in general, since it reduces to 3SAT. However, there are a ...
5
If the answer to the first question were to be yes, then $P=NP$, as stated in nir shahar's answer. This has not been done.
"The easiest NP hard problem"
However you next asked if any NP-hard problems have been solved in close to polynomial time, for which you might love to learn about what has been called "The easiest NP hard problem" ...
0
For item (b), the reduction does not work. To understand why, imagine a graph with all edges having the same weight. Then, the reduction has no effect: $G = G'$. Finding the shortest path from $u$ to $v$ consists in finding the path with fewer intermediate nodes, while finding the longest path, consists in finding the path with the highest number of ...
4
Strictly speaking, as the other answers explain, no. A polynomial-time algorithm for an NP-hard problem is not known nor expected to exist. But I think your underlying question is whether or not there are examples of natural NP-hard problems that are, in some sense, easier to solve than some other NP-hard problems.
There are several flavors in which you can ...
10
By definition, if you were to find a polynomial time algorithm for an NP-hard (or NP-complete) problem, then $P=NP$. So, short answer is - no.
However, its possible to think instead of solving the problems fully, to approximate a solution, or to solve them randomly. There are attempts at attacking from those points of view, but they are not perfect at all. ...
4
Take a look at the FP complexity class.
Technically speaking, it is wrong. However, usually people don't make a huge difference between the two. Its usually clear from the context whether the problem is a decision or a search problem, hence its clear whether it should be in $P$ or $FP$.
So, writing that "Finding the shortest $(s,t)$ path in the graph $G$...
1
One-way functions need not be invertible. A one-way function which is invertible is known as a one-way permutation.
Here is the definition of one-way function from Goldreich's primer:
A function $f\colon \{0,1\}^* \to \{0,1\}^*$ is one-way if it can be computed in polynomial time, and is hard to invert: for every polynomial time algorithm $A$, $$ \Pr_{x \in ...
1
The counting problems corresponding to your two decision problems are:
Given a partially filled Latin square, in how many ways can it be completed to a Latin square?
Given a partially filled Sudoku puzzle, in how many ways can it be completed to a Sudoku solution?
3
You can naively compute ALL-SAT in $2^npoly(n,m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. You clearly need $\Omega(2^n)$ time in the worst case just to write down the assignments (in the case of a tautology). If the strong exponential time hypothesis (SETH) holds, then this is not much harder than SAT itself, so under ...
3
Assuming $\le_P$ is a polynomial many-one reduction (as opposed to a Turing reduction), the statement is incorrect.
For example, for any language $L$ we have $\overline{L} \in P^L$ (and in fact, in $O(1)$ time and space as well, so this is also an example for logspace many-one reductions)
But obviously if we take $L=\mathrm{Halt}$ to be the halting problem ...
3
It does not reach a constant ceiling, but the modulo gate cannot depend on the input's length, e.g. $\bmod n/2$ gates are not allowed. You must decide on the constants while constructing the circuit, independently of the input/input size. See the definition in Arora and Barak's book, where they first define $ACC0(m_1,...,m_k)$ which corresponds to circuits ...
3
An $n^k$ prover implies that the set $\{\left(\varphi,1^n\right)|\text{$\varphi$ has a proof of length $\le n$}\}$ is in $P$, since we can simply run the prover for $n^k$ steps and check whether it yields a valid proof.
It remains to show that this language is NP complete. This follows from a straightforward reduction from SAT. Given a CNF $\varphi$ over the ...
2
The special case where $v=0$ and $Y=\{\frac12\sum_{i=1}^m x_i\}$ is the partition problem, which is NP-complete.
0
The usual proof that STCON is in NL works as follows: you guess a path from $u$ to $v$, and verify it step by step.
A very similar proof works for 2STCON: you guess two paths from $u$ to $v$, and verify them step by step. As you verify them, you also verify that they are different: either the length is different, or the $i$-th vertex is different, for some $...
0
Start by initializing a boolean array $T$ with indices from $0$ to $b$, inclusive. $T_0$ starts as true (because you can always achieve a sum of 0) and the rest of the array starts as false.
For each value $a_i$, we update the array by going though each value $x$ where $x+a_i\leq b$, and setting $T_{x+a_i}$ to true only if $T_x$ is true.
Essentially, at any ...
2
The circuit $C_n$ has $n+m$ inputs, $x_1,\ldots,x_n,r_1,\ldots,r_m$. Its size is polynomial in $n$, so without loss of generality, $m$ is polynomial in $n$. What we want is:
If $f_n(x) = 0$ then $\Pr_r[C_n(x,r) = 0] = 1$.
If $f_n(x) = 1$ then $\Pr_r[C_n(x,r) = 1] \ge 1/2$.
Here $x$ is shortcut for $x_1,\ldots,x_n$, and $r$ is shortcut for $r_1,\ldots,r_m$.
2
Interpreting your problem as finding a computable $f$ such that $f\big(\langle M\rangle\big)=\langle M'\rangle$ with the property that $M'$ enumerates all programs equivalent to $M$, i.e. all $M''$ with $L(M'')=L(M)$, the answer is no (such $f$ does not exist).
One way to show this is to observe that such $f$ would place the language $\left\{\big(\langle M_1\...
1
You should think in Turing Machines.
If I understand correctly, what you ask is more or less "Given the code of a Turing Machine, is it possible to enumerate the codes of all Turing Machines with the same language?".
I think this is not possible, because it is undecidable to know whether two TM have the same languages (all the more so list all TM ...
0
An oracle access to a random oracle can simulate the effect probabilistic TM's have. However, oracle machines aren't limited to using a random oracle, you can specify whatever oracle you would like, to any problem - no matter how hard the problem is, and a TM with an oracle access to it would solve it in constant time.
So, in this line of thinking - an ...
3
A description is given in the first paragraph of [1], where HI stands for Hypergraph Isomorphism and GI for Graph Isomorphism:
Given a pair of hypergraphs $X=(V,E)$ and $X'=(V',E')$ as instance for HI, the reduced instance of GI consists of two corresponding bipartite graphs $Y$ and $Y'$ defined as follows. The graph $Y$ has vertex set $V \uplus E$ and edge ...
1
With regards to (3), there's a fairly simple algorithm to compute large exponents.
exp(a, b) =
if b is even
let half = exp(a , b/2)
return half * half
else
return a * exp(a, b-1)
This will be logarithmic in the magnitude of $b$, meaning the number of multiplications is linear in the number of bits used to represent $b$. It's also a very ...
1
Since $T(n)=T(n-1)$, using induction we can prove that $T(n)= 1 + \sum_{k=1}^n k(k-1) \le 2\sum_{k=1}^n k(k-1)$
Now, calculating $\sum_{k=1}^n k(k-1)$ gives us:
$\sum_{k=1}^n k(k-1)=\sum_{k=1}^n (k^2 - k) = \sum_{k=1}^n k^2 - \sum_{k=1}^n k$
Using this formula, we know that $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$, and its not hard to show that $\sum_{k=1}...
3
You are correct that $\emptyset\in NP$, since we already know that $\emptyset$ can be decided in constant time (a TM that immediately rejects), and $DTIME(O(1))\subseteq P\subseteq NP$.
But $\emptyset$ is not NP-complete, regardless of whether $P=NP$. Indeed, by definition, a NP-complete language $A$ is such that every language $B \in NP$ admits a Karp ...
2
Count the number of times each of the 5 new element is moved in the array:
The areay is of length $n$, and thus each of the 5 elements move at most $n$ times. The place of all other elements is correct, and thus there is at most $5n$ swaps required to "correct" the array, hence $O(n)$ swaps.
4
I don't know precisely how Bob works, but let's talk about clause learning.
Suppose you have a set of variable assignments, $A$, say $x_1 = 0$, $x_2 = 1$, $x_3 = 0$. This is a single clause in disjunctive normal form:
$$A = \neg x_1 \wedge x_2 \wedge \neg x_3$$
The negation of this set of assignments is a single clause in conjunctive normal form:
$$\neg A = ...
4
Suppose that P=NP, and that $f\colon \{0,1\}^* \to \{0,1\}^*$ is an arbitrary function computable in polynomial time. Suppose that $|x| = n$, and we are given $y = f(x)$. We will show how to find $z \in \{0,1\}^n$ such that $y = f(z)$ in polynomial time (in $n$).
Using an NP oracle, we determine whether there exists $z$ such that $z_1 = 1$ and $y = f(z)$. If ...
2
Color the vertices in $V \setminus X$ with $2k$ colors at random. With probability $e^{-2k}$, the $V \setminus X$ vertices of your $k$ disjoint triangles will be highlighted.
Suppose without loss of generality that $X = [m]$.
Using dynamic programming, determine for each subset $S \subseteq [2k]$ and $i \in [m]$ whether there exist $|S|/2$ disjoint triangles ...
1
If $A$ is an algorithm whose running time is $O(1/\epsilon)$, then if you substitute $\epsilon = 1/n$, its running time will be $O(n)$. This is a property of the particular algorithm $A$ rather than of polynomial time approximation schemes. We have absolutely no guarantee on the running time of a PTAS when $\epsilon$ is subconstant (i.e., when $\epsilon = o(...
2
If you treat a SAT solver as being reasonably efficient and you can invoke it multiple times, then you can solve arbitrary problems in $P^{NP}$ (trivially; SAT lets you solve any problem in NP, and $P^{NP}$ is exactly the class of problems you can solve by invoking an oracle for a NP-complete problem multiple times).
2
We don't know that PH doesn't collapse to NP. We don't even know that PH doesn't collapse all the way to P.
The best you can say is that you can use SAT solvers to solve problems in one of these classes iff PH collapses to NP.
2
This is a very simple question, I will explain steps-by-steps:
First, you need to count total elements and total comparisons in your tree
Second, you need to know that for each element in the tree, it takes $\frac{total \ comparisons}{total \ elements}$ average comparisons to search for an element in the tree.
Third, if the problem gives you a probability to ...
1
Equivalence follows immediately from the definitions. The definition of $\setminus$ is:
$$A \setminus B = A \cap \overline{B}$$
where $\overline{B} = \Sigma^* \setminus B$ denotes the complement of $B$. Now taking $L_1=A$ and $L_2=B$, it is trivial to prove that $L$ meets the first definition iff it meets the second definition, since $B \in NP$ iff $\...
Top 50 recent answers are included
