Questions tagged [polynomial-time]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
27
votes
2answers
1k views

Finding a prime greater than a given bound

Is a deterministic polynomial-time algorithm known for the following problem: Input: a natural number $n$ (in binary encoding) Output: a prime number $p > n$. (According to a list of open ...
31
votes
2answers
942 views

What classes of mathematical programs can be solved exactly or approximately, in polynomial time?

I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The ...
15
votes
3answers
2k views

Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)

Answer: not known. The questions asked are natural, open, and apparently difficult; the question now is a community wiki. Overview The question seeks to divide languages belonging to the complexity ...
13
votes
3answers
893 views

Which Integer Linear Programs are easy?

While trying to solve a problem, I ended up expressing part of it as the following integer linear program. Here $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ are all positive ...
8
votes
4answers
757 views

What are some efficient algorithms for determining if a quadratic multivariate polynomial has a solution?

I know that in general, multivariate polynomial satisfiability is equivalent to 3-SAT; however, I'm wondering if there are any good techniques in the quadratic case, specifically if there is a ...
8
votes
1answer
425 views

Are there more polynomial time problems with complexity lower bounds?

I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below. Exponential Lower Bounds: Claim: If ...
67
votes
4answers
31k views

Why is 2SAT in P?

I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...
23
votes
7answers
3k views

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

László Babai recently proved that the Graph Isomorphism problem is in quasipolynomial time. See also his talk at University of Chicago, note from the talks by Jeremy Kun GLL post 1, GLL post 2, GLL ...
20
votes
5answers
752 views

What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
23
votes
1answer
1k views

For which k is PLANAR NAE k-SAT in P?

The Not All Equal $k$-SAT problem (NAE $k$-SAT), given a set $C$ of clauses over a set $X$ of boolean variables such that each clause contains at most $k$ literals, asks whether there exists a truth ...
8
votes
3answers
649 views

Non-Orthogonal Vectors Problem

Consider the following problems: Orthogonal Vectors Problem Input: A set $S$ of $n$ Boolean vectors each of length $d$. Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
30
votes
2answers
844 views

Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

I would like to find a polynomial time algorithm that determines if the span of a given set of matrices contains a permutation matrix. If any one knows if this problem is of a different complexity ...
22
votes
3answers
2k views

How fast can we solve a totally unimodular integer linear program?

(This is a follow-up to this question and its answer.) I have the following totally unimodular (TU) integer linear program (ILP). Here $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ ...
12
votes
1answer
1k views

NP-hardness of a special case of Number Partitioning

Consider the following problem, Given a set of $n = k m$ positive numbers $\{ a_1, \dots, a_n \}$ in which $k \ge 3$ is a constant, we want to partition the set into $m$ subsets of size $k$ so that ...
8
votes
1answer
372 views

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

In what cases $\mathsf{SAT}$ can be solved in polynomial time? I know two cases: $2$-$\mathsf{SAT}$ and Horn-$\mathsf{SAT}$. Question 1: Is there a reference with algorithms for solving $\mathsf{...
4
votes
5answers
580 views

Problems that are hard to prove in $\mathcal{P}$

What is the famous "hard" problems that were shown to be in $\mathcal{P}$ after? I want to know a list of problems that are difficult to prove in the class of "easy" problems? Maybe like matching, ...
5
votes
1answer
361 views

A reachability problem

Let $P$ be a length-preserving (i.e. $|P(x)|=|x|$) polynomial-time computable program. I. Given two strings $x$ and $y$, we want to decide if $y$ can be obtained by repeated applications of $P$ ...
2
votes
0answers
154 views

What are some efficient algorithms for finding the solutions to a quadratic multivariate polynomial?

Based on this question, there's an efficient algorithm to determine whether a quadratic multivariate polynomial has a root. What are some algorithms to enumerate these solutions? I'm interested in ...
0
votes
1answer
159 views

What are some efficient algorithms for determining if a system of quadratic multivariate polynomials have a solution?

I know that in the general case it isn't efficient. However, I'm wondering if there are any good techniques in the quadratic case over the reals, specifically if there is a polynomial time solution.
-1
votes
1answer
176 views

Any result connecting an NP-complete problem with slight super-polynomial time?

Helo everybody, is there any result or research that connects some $NP$-complete problem with only slightly super-polynomial (strongly sub-exponential) time? This would not necessarily involve ...