# Tag Info

38

An algorithm is polynomial (has polynomial running time) if for some $k,C>0$, its running time on inputs of size $n$ is at most $Cn^k$. Equivalently, an algorithm is polynomial if for some $k>0$, its running time on inputs of size $n$ is $O(n^k)$. This includes linear, quadratic, cubic and more. On the other hand, algorithms with exponential running ...

27

The short answer: because you can use Integers to simulate Booleans for SAT, but when you don't restrict yourself to this, then you can't actually simulate SAT. You'll get a feasible answer, but it no longer carries any meaning in terms of whatever SAT instance you were trying to simulate. The tough answer to this is that we don't know that they aren't in ...

22

The reason linear programming is "efficient" is that the solution space may be represented by a single convex polyhedron. If one is trying to find the "highest" vertex on that polyhedron (one may apply a linear transform to any linear programming problem to make "height" correspond to the quantity to be maximized), then from any vertex one may travel along ...

22

Two decades ago, one of the plausible answers would be primality testing: there were algorithms that ran in randomized polynomial time, and algorithms that ran in deterministic polynomial time under a plausible number-theoretic conjecture, but no known deterministic polynomial-time algorithms. In 2002, that changed with a breakthrough result by Agrawal, ...

20

So your problem is as follows: Input: integers $\ell,u$ Question: does there exist a prime in $[\ell,u]$? As far as I know, it is not known whether that problem is in P or not. Here's what I do know: Primality testing (given a single number, test whether it is prime) is in P, so if the range is small enough, you can exhaustively test each number in the ...

20

You are misunderstanding how accepting a language works. A language $L$ is in P iff there is a deterministic Turing Machine that decides whether a word $w$ belongs to $L$ in polynomial time. Deciding means that it return a positive answer iff $w \in L$ and a negative otherwise. Your approach will return a positive answer in every case. Thus your TM will ...

17

What this means is that unary knapsack is in P. It does not mean that knapsack (with binary-encoded numbers) is in P. Knapsack is known to be NP-complete. If you showed that knapsack is in P, that would show that P = NP. But you haven't shown that knapsack is in P. You've shown that unary knapsack is in P. However, unary knapsack is not known to be NP-...

15

I can't comment since it requires 50 rep, but there are some misconceptions being spread about, especially Raphael's comment "In general, a continous domain means there is no brute force (and no clever heuristics to speed it up)." This is absolutely false. The key point is indeed convexity. Barring some technical constraint qualifications, minimizing a ...

15

Yes, it is true. In terms of complexity classes, $$\text{REG} \subseteq \text{P},$$ where $\text{REG}$ is the class of regular languages (i.e., problems that can be solved by a finite automaton). More specifically, $$\text{REG} \subseteq \text{DTIME}(n), \tag{*}$$ and $\text{DTIME}(n)$ is a strict subset of $\text{P}$ by the time hierarchy theorem. The ...

14

The most common technique is to prove that the problem is hard for some class. For example, consider the problem HALT in which we are given a Turing machine $T$ and a number $n$ (encoded in binary, i.e., in the usual way), and the task is to decide whether $T$ halts within $n$ steps. HALT is EXPTIME-hard. If HALT were in P then P=EXPTIME (using the EXPTIME-...

14

$(3,k)\text{-LSAT}$ is in P for all $k$. As you have indicated, locality is a big obstruction to NP-completeness. Here is a polynomial algorithm. Input: $\phi\in (3,k)\text{-LSAT}$, $\phi=c_1\wedge c_2\cdots \wedge c_m$, where $c_i$ is the $i$-th clause. Output: true if $\phi$ becomes 1 under some assignment of all variables. Procedure: Construct set $B_i$...

13

Make a BFS/DFS traversal on the graph. If you visited every vertex then it is connected otherwise not. Note: You have to apply BFS/DFS only one time on the graph

13

Your confusion is that the class #P only asks you to count the solutions, not to enumerate them, and you only need $n$ bits to write down the number $2^n$. This means that to express the number of satisfying assignments to a formula of $n$ variables, you need $n$ bits, because there are at most $2^n$ solutions (i.e. in the case of a tautology). Another ...

12

Theoretically speaking, this is impossible to accomplish, basically because "polynomial" and "exponential" are asymptotic concepts, and no prefix of the data guarantees anything about the behavior at infinity. Practically speaking, you can try to compute $t(n)^{1/n}$ and so if it approaches a constant bounded away from 1. If so, it is exponential. To test ...

12

There is no fixed terminology for these types of functions. You might sometimes see "subexponential" or "superpolynomial" used to refer to this kind of behavior.

12

A simple answer is "binary search". Keep track of a lower bound (starts out with 1) and an upper bound (starts out with $n$). In each iteration compute the midpoint $m$. In polytime check if $mâˆ—m=n$. If so, terminate. Otherwise, if $mâˆ—m>n$ reduce the upper bound to $m$, else increase the lower bound to $m$. If the upper bound and the lower bound become ...

12

It's a tough question, because there isn't a consensus. There are still people who conjecture that $P=NP$. But in my mind, the most notable problem with a significant conjecture that it's in $P$ is Graph Isomorphism But, again, nobody really knows. In general, the "conjecture that it's in $P$ " is going to be rare. We only conjecture that a problem is in ...

12

This problem is still open. See for example Wikipedia, which while not a dependable source in general, will probably be updated if a strongly polynomial time algorithm is ever found.

10

For the shortest path problem, if we do not care about weights, then breadth first search is a surefire way. Otherwise Dijkstra's algorithm works as long as there are no negative edges. For longest path, you could always do Bellman-Ford on the graph with all edge weights negated. Recall that Bellman-Ford works as long as there are no negative weight cycles,...

10

The conversion from CNF to DNF can come at an exponential cost. For example $(a_1 \lor b_1) \land \cdots \land (a_n \lor b_n)$ expands to $2^n$ many terms. As you comment, for DNF satisfiability is easy - it is falsifiability which is hard. If the problem is trivial, you don't input it to a SAT solver, and that's why SAT solvers accept CNFs instead of DNFs. ...

10

Typically, we use $\alpha < 1$ for maximization problems, and $\alpha > 1$ for minimization problems, where $\alpha$ is the approximation guarantee. So, a $2$-approximation algorithm returns a solution whose cost is at most twice the optimal. But as always, to be absolutely sure, go back to the definitions of the text you are reading (if a definition ...

9

An NP-complete problem can be transformed into another NP-complete problem. There's an abundance of known NP-complete problems, in fact, one could even say that any really interesting problem is NP-complete. So if you know of a way of solving any NP-complete problem $X$ quickly, you can take any other NP-complete problem, transform it into an instance of $X$,...

9

Regarding your first question, what you're missing is where your "exponential table" comes from. Your algorithm has a finite description and should work for every $n$. So it cannot explicitly contain the $n$-table for all $n$. It could contain instructions for computing the table, but then it would have to first execute them, and constructing an exponential ...

9

To show a new problem $X$ is hard, you reduce from a problem of known hardness to $X$. For example, you can show $X$ is hard by reducing 3-SAT to $X$. The general idea is that if you had an efficient algorithm for solving $X$, you could also solve instances of 3-SAT efficiently. This is so because you can exhibit a polynomial time transformation from a 3-...

9

This algorithm doesn't run in polynomial time, it runs with polynomial delay. As the paper notes: Observe that the number of minimal, and even minimum solutions, can be exponential in the size of the graph; Fig. 1 gives an example. Therefore, the total running time of any enumeration algorithm cannot be expected to be polynomial in the size of the ...

9

Since this question was reopened and made more explicit, I would like to convert my comment into an answer. Now the OP wants to understand why and when polynomial algorithms became of interest. I especially focus on the sub-question: When did people realize the role and importance of efficient versus non-efficient algorithms? Because algorithms, in ...

9

If $\mathsf{NTIME}(n^k) \subseteq \mathsf{TIME}(n^\ell)$ for any $k,\ell$ then $\mathsf{P} = \mathsf{NP}$. Indeed, any problem $L \in \mathsf{NP}$ can be solved in non-deterministic time $O(n^r)$ for some $r$. Consider now the problem $L' = \{0^{|x|^{r/k}}1x : x \in L\}$. Clearly this problem is still in $\mathsf{NP}$, and furthermore the previous algorithm ...

9

The comment is wrong. It is very easy to give examples of polynomial time algorithms which aren't practical at all: The ellipsoid algorithm for solving linear programs runs in polynomial time but is too slow to be practical. The simplex algorithm, whose worst-case running time is exponential, is preferred in practice. The AKS primality testing algorithm ...

9

You're not wrong, you're just using a different cost model. Typically there are two: Uniform cost model - assigns a constant cost to every machine operation regardless of size of numbers. Logarithmic cost model - assigns a cost proportional to the number of bits involved for each machine operation. Under uniform cost, a binary search takes ...

8

Let $n = |V(G)|$ and $m = |E(G)|$. Let $w(a \to b)$ denote the weight of the edge $(a \to b)$. Suppose that you want to find the minimum and maximum path cost from $s$ to $t$. Starting from $b := t$, perform the following: If $b$ has already been visited, return the already computed $\min(b)$ and $\max(b)$. Otherwise mark $b$ as visited. Determine and ...

Only top voted, non community-wiki answers of a minimum length are eligible