# Tag Info

## Hot answers tagged polynomial-time

34 votes

### Magic constant to solve NP-complete problem in polynomial time

Probably not. What you are asking is whether NP $\subset$ P/poly. If this were true, then the polynomial hierarchy would collapse (this is the Karp–Lipton theorem), something that is widely believed ...
• 50.3k
29 votes
Accepted

### Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

Yes, this is known. It appears in one of the must-cite references on triangle finding... Namely, Itai and Rodeh show in SICOMP 1978 how to find, in $O(n^2)$ time, a cycle in a graph that has at most ...
• 26.5k
26 votes

### Is there a natural problem in quasi-polynomial time, but not in polynomial time?

There has, in fact, been quite a lot of recent works on proving quasi-polynomial running time lower bound for computational problems, mostly based on the exponential time hypothesis. Here are some ...
23 votes

### Is there a natural problem in quasi-polynomial time, but not in polynomial time?

Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, ...
22 votes
Accepted

### Time complexity with irrational exponent?

While admittedly I haven't done the analysis, and this is not strictly a decision problem, I am willing to wager the best known matrix multiplication algorithms (by Coppersmith, Winograd, Stothers, ...
• 2,295
20 votes
Accepted

### Counting the number of satisfying assignments in a POSITIVE CNF-SAT

This is still #P-complete [1]. This problem is usually referred to as montone (#)SAT. Monotone #2-SAT is already #P-complete (this is equivalent to counting vertex covers of a graph). [1] Roth, Dan. "...
• 1,855
17 votes

### Are there interesting graph classes where the treewidth is hard (easy) to compute?

Treewidth is NP-hard to compute on co-bipartite graphs, indeed the original NP-hardness proof of treewidth of Arnborg et al. shows this. Additionally, Bodlaender and Thilikos showed that it is NP-hard ...
• 3,236
16 votes
Accepted

### What notable automaton models have polynomially-decidable containment?

Visibly pushdown automata (or nested word automata, if you prefer working with nested words instead of finite words) extend the expressive power of deterministic finite automata: the class of regular ...
• 5,444
15 votes
Accepted

### What is an equivalent definition of mP/poly in terms of a Turing machine?

There is a notion of a monotone non-deterministic and, more generally, alternating Turing machine in the paper Monotone Complexity by Grigni and Sipser. Since polynomial time is the same as ...
• 4,511
15 votes

### Counting the number of satisfying assignments in a POSITIVE CNF-SAT

This problem is Monotone-SAT. It is #P-Complete under Cook Reductions. It is one of those problems that are "easy to decide but hard to count." I recommend the following paper. Self-Reducibility of ...
• 2,579
14 votes

### What notable automaton models have polynomially-decidable containment?

If infinite words are in your scope, you can generalize DFA (with parity condition) to the so-called Good-for-Games automata (GFG), that still have polynomial containment. A NFA is GFG if there is a ...
• 7,682
14 votes
Accepted

### On theoretical aproaches for solving $\mathsf{SAT}$ in special cases

Concerning Question 1, there have mainly been two lines of work to find tractable restrictions of SAT. The first one that you are already familiar with is to restrict the types of the clauses that ...
• 1,855
13 votes

### Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

It's not quadratic, but Alon Yuster and Zwick ("Finding and counting given length cycles", Algorithmica 1997) give an algorithm for finding triangles in time $O(m^{2\omega/(\omega+1)})$, where $\omega$...
• 50.3k
13 votes
Accepted

### Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?

How bout the simplex algorithm for linear programming? In many occasions it is used in practice. Edited to add: I think it's more of a "worse-case exponential algorithm" which runs ...
• 9,378
13 votes
Accepted

### questions on implications Babais quasi P time graph isomorphism result

Johnson graphs are actually easy to recognize. In particular, you can recognize whether an input graph is a Johnson graph in polynomial time, and you can construct an isomorphism between two ...
• 14.1k
12 votes

The fastest algorithm known for the problem of identifying whether a graph has a knotless embedding is due to Miller and Naimi, and is exponential-time. Robertson-Seymour theory says that there is an $... • 23.7k 12 votes ### Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs) Group Isomorphism! Although Ricky Demer gave lots (though certainly not all) details on this, there is an important point I want to highlight, esp. given the stated motivation for the question, namely:... • 35.8k 12 votes Accepted ### What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages? If$\mathrm{P\subseteq CSL}$, then$\mathrm{P\subseteq DSPACE}(n^2)$. By a padding argument, this implies $$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}\bigl(t(n)^\epsilon\bigr)$$ for every ... • 14.8k 11 votes ### Is there a natural problem in quasi-polynomial time, but not in polynomial time? Computing VC dimension seems unlikely to be in polynomial time, but has a quasipolynomial time algorithm. Also, it seems hard to detect a planted clique of size$O(\log n)$in a random graph, but ... • 2,295 11 votes ### What notable automaton models have polynomially-decidable containment? A Non deterministic XOR automaton (NXA) fits your question. A NXA$M$is essentially an NFA, but a word$w\in \Sigma^*$is said to be in$L(M)$if it is accepted by an odd number of paths (Xor ... • 9,378 11 votes ### Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs) Solving the planted clique problem of distinguishing a uniformly random graph from the union of a random graph and a clique (of size intermediate between$2\log_2 n$and$\sqrt n$), with success ... • 50.3k 11 votes Accepted ### On sparse complete sets and P vs L Yes, exactly what you suggested is true: if there is a sparse$\mathbf{P}$-complete set under log-space many-one reductions, then$\mathbf{P} = \mathbf{L}$. This was conjectured by Hartmanis in 1978 ... • 1,733 10 votes ### Choosing random permutations in "strict" polynomial time If the only randomness you can obtain is sampling from a set of polynomial size, you are not going to be able to get two random permutations, because the probability of any particular pair of random ... • 23.7k 9 votes Accepted ### Is there a generalization of information theory to polynomially knowable information? Yes. Time-bounded Kolmogorov complexity is at least one such "generalization" (though strictly speaking it's not a generalization, but a related concept). Fix a universal Turing machine$U$. The$t(n)$... • 35.8k 9 votes Accepted ### What are the consequences of$P \subseteq L/poly$? One simple consequence is$\mathbf{P}/\text{poly} = \mathbf{L}/\text{poly}$. Proof: For any language$A \in \mathbf{P}/\text{poly}$, there is a language$B \in \mathbf{P}$and a sequence of polynomial-... • 1,733 8 votes ### Is there a natural problem in quasi-polynomial time, but not in polynomial time? If the exponential time hypothesis is correct (or even weaker versions), then one can not solve 3SAT for instances with polyglog number of variables in polynomial time. Of course, quasi-polynomial ... • 9,566 8 votes ### Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs) Approximating the Directed Steiner tree problem to within a poly-logarithmic factor. Currently there is a quasi-polynomial time algorithm that gives an$O(\log^3 k)$-approximation. More precisely, one ... • 6,659 8 votes ### Non-Orthogonal Vectors Problem When$k$is given as part of the input, the second problem is equivalent to the monochromatic Max-IP problem (given$S \subseteq \{0,1\}^d$, find$\max_{(a,b) \in S, a\ne b} a \cdot b\$). Recently I ...
• 121

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