Questions tagged [polynomial-time]
The polynomial-time tag has no usage guidance.
85
questions
1
vote
1answer
93 views
Induction on all polynomial runtimes?
Has there ever been a proof technique to show that a language isn't in $\mathrm{P}$, by showing inductively there isn't any $k$ for which the language is in $\mathrm{TIME}(n^k)$?
e.g.: $L\notin \...
10
votes
0answers
172 views
On Courcelle's question about Monadic second-order logic with cardinality predicates
I have found the following question at openproblemgarden.org:
The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the ...
6
votes
1answer
318 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{...
10
votes
2answers
180 views
“Relatives” of the shortest path problem
Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such ...
0
votes
0answers
54 views
When can convex optimization be considered to be exactly solvable?
If one is trying to find the global minima of a convex function using gradient descent then one will get a run-time which is a function of $\epsilon >0$ where $\epsilon$ measures the accuracy of ...
1
vote
0answers
96 views
How to prove a general convex set is nonempty or empty in polynomial time?
The general convex set should be represented by a set of (generalized) inequalities $f_{i}(x)\leq 0 $ with $ f_{i}(x) $ being convex in $ x $.
I know ellipsoid method and interior method, but I do ...
2
votes
0answers
52 views
Complexity of comparing extended integer power towers
Inspired by this stackexchange question, is it an open problem to compare two power towers of positive integers if we additionally allow numbers lower in the tower to themselves be represented by ...
8
votes
0answers
231 views
Subset sum problem with at most one solution for any target
This question was originally asked on CS.se. A little bit of initial discussion can be found in the comments there.
We first consider the search version of the subset sum problem: Given a set $S$ of ...
4
votes
1answer
143 views
Generalizations of linear programming
Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs.
Is there a survey/lecture notes describing ...
10
votes
1answer
190 views
P and Descriptive Complexity
In the Complexity Zoo, it says [1] that, in descriptive complexity, $P$ can be defined by three different kind of formulae, $FO(LFP)$ which is also $FO(n^{O(1)})$, and also as $SO(HORN)$.
However, ...
3
votes
0answers
109 views
Is Circuit Minimization $P$-hard under logspace reductions?
By Circuit Minimization, I am referring to the following decision problem.
Circuit Minimization
Input: A bit string $x$ and a number $k$.
Question: Does there exist a Boolean Circuit $C$...
7
votes
1answer
115 views
Why is the “general notion of a reduction […] inherent to the notion of self-reducibility”?
While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around:
Note that the general ...
5
votes
1answer
125 views
Complexity of counting integer roots of multivariate polynomials in a polyhedron?
Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials in $\mathbb Z[x_1,\dots,x_m]$ with both $m$ and total ...
4
votes
1answer
78 views
Complexity of finding Exact Size Cut-Sets in Bipartite Graphs
I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...
8
votes
3answers
413 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$ ...
0
votes
0answers
112 views
What definition for $FPT$ algorithm for $KSUM$ gives $W[P]=FPT\implies KSUM$ is $FPT$?
In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$.
$KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey ...
1
vote
1answer
114 views
Can MONOTONE WSAT be in solved in polynomial time?
In the weighted monotone satisfiability problem (MONOTONE WSAT), the input is an n-variable MONOTONE CNF Boolean formula (when there is no a clause with a negated variable) and an integer k, and the ...
3
votes
1answer
128 views
On complexity of linear programming with quadratic equality/inequality constraints?
Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ ...
4
votes
0answers
125 views
Reduce $m$-clause 3SAT to PLANAR-3SAT in $O(m^{2-\varepsilon})$
The classic reduction from 3SAT to PLANAR-3SAT requires a removal of $O(m^2)$ crossings from a rectilinear representation of 3SAT with $m$ clauses. However, the crossing number inequality suggests ...
10
votes
1answer
151 views
On sparse complete sets and P vs L
Mahaney's Theorem tells us that if there is a sparse $NP$-complete set under polynomial-time many-one reductions, then $P = NP$. (See "Sparse complete sets for NP: Solution of a conjecture of Berman ...
14
votes
1answer
205 views
What are the consequences of $P \subseteq L/poly$?
A language is in $L/poly$ if there exists a logspace Turing machine that decides the language with polynomial amount of advice.
See here for more info: https://en.wikipedia.org/wiki/L/poly
...
2
votes
0answers
103 views
On $\Sigma \Pi \Sigma \Pi(2,r)$-circuits
As I understand from the survey "Progress on Polynomial Identity Testing - II"
a polynomial-time algorithm for solving PIT for $\Sigma \Pi \Sigma \Pi (2, r)$ is unknown.
However, there exists paper ...
1
vote
0answers
84 views
Time complexity of polynomial regression with random coefficients
Suppose that I have
$$\lim_{k,l,m \rightarrow \infty}(f(x,l) ~~=~~ \sum_{n=1}^{m} g(a_{n,k})h(x,n)$$
where the $a_{n,k}$ are pseudo-random real numbers with $k$ digits generated in an arbitrary way, ...
5
votes
0answers
356 views
Do we know some quasi-polynomial problem that is known to not be in NP?
The title pretty much says it all, but to explain how I got there:
I think, that one of the reasons we are unable to prove or disprove , but mainly disprove $P=NP$ (and yes, I was provoked by the ...
6
votes
1answer
140 views
Bounded distance decoding beyond Babai
Consider a full-rank lattice in $\mathbb{R}^n$. Let $\lambda_1$ be the length of the shortest nonzero vector. Given a vector in $\mathbb{R}^n$ we wish to find the nearest lattice vector, as measured ...
13
votes
2answers
752 views
Counting the number of satisfying assignments in a POSITIVE CNF-SAT
We know the problem of counting the number of satisfying assignment in a given general boolean formula (CNF-SAT), a given DNF formula, or even a given 2SAT formula is a #P-complete problem.
Now, ...
7
votes
1answer
242 views
Using an oracle to find a vector $b$ for which $Ax=b$ has a solution
There is an oracle built around a hidden $m\times n$ matrix $A$ all of whose entries are 0 or 1, where $m>n$. The oracle takes as input an integer vector $b$ with positive entries, and answers as ...
13
votes
1answer
561 views
Are there interesting graph classes where the treewidth is hard (easy) to compute?
Treewith is an important graph parameter that indicates how close a graph is from being a tree (although not in a strict topological sense).
It is well known that computing the treewidth is NP-hard.
...
7
votes
0answers
276 views
Under what conditions does an Integer Programming problem run in polynomial time?
Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in ...
5
votes
2answers
363 views
On integer programming
Integer programming is NP-hard.
What is the status of integer programming problem that decides between existence of $\leq1$ solution and $>1$ solutions (note $0$ solutions falls in $\leq1$ ...
10
votes
1answer
200 views
What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages?
It is unknown whether $P\subseteq CSL$ or $P\not\subseteq CSL$, where
$P$ is the set of all languages decidable in polynomial time on a deterministic Turing machine, and
$CSL$ is the class of context-...
-2
votes
1answer
210 views
questions on implications Babais quasi P time graph isomorphism result
Babai has reputedly repaired his proof of graph isomorphism in quasipolynomial time.[1] the proof hinges crucially on Johnson graphs.
based on the proof, does this mean now that if Johnson ...
1
vote
1answer
667 views
Is the value of $\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf}$ polynomially computable?
For a graph $G$ on $n$ vertices, what is the value of following ratio:
$$\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf} ,$$
where $L_G=D_G-A_G$ is ...
9
votes
0answers
171 views
Wide and shallow circuits for $\mathrm P$
The $\mathrm{NC} \stackrel?= \mathrm P$ question is not as famous as the $\mathrm P$ versus $\mathrm{NP}$ problem, but still a deep and interesting question. It is generally accepted that there are ...
4
votes
0answers
101 views
$\mathsf{P}$ is the closure of [finite set] under [operation between languages]
I am searching for statements of the above form, that is, asserting the existence of a finite set $F$ of languages and one or more operations $\otimes\colon \mathcal{P}(\Sigma^*) \times \mathcal{P}(\...
2
votes
1answer
341 views
Graph planarity testing via adjacency matrix
I have looked at several efficient graph planarity algorithms which
rely on computing and traversing DFS trees
(that add one vertex/edge/path at a time).
I am looking for graph planarity algorithms ...
6
votes
1answer
217 views
Two extremely naive questions about the Kronecker problem from Geometric Complexity Theory
I was reading the GCT IV paper (http://arxiv.org/pdf/cs/0703110v4.pdf) and while the representation theory is clear enough (by which I do not mean to say 'easy'!) the relation to complexity theory as ...
0
votes
2answers
345 views
Packing $n$ objects into $m$ bins whose size is variable
Assume we have $n$ fixed size objects with sizes $O_1$ to $O_n$. Also, assume we have $m$ bins with size $a \times B_1$ to $a \times B_m$ in which $a$ is a real number and $a\ge1$. We want to put ...
3
votes
0answers
51 views
Ground Reachability in String and Term Rewriting Systems
I have two questions concerning ground reachability in string and term rewriting systems.
String Rewriting Systems:
Let $\Sigma$ be a finite alphabet.
I have a set of rules $R$ of the form $a_ib_i =...
4
votes
0answers
192 views
Voronoi diagram in presence of polygonal obstacle
Suppose there is a set of convex polygons ($\mathbb{P}$) on the plane. For each convex polygon $P_i$ there is one "facility" $f_i$ placed on the boundary of $P_i$.
The distance between a point $p \in ...
4
votes
1answer
556 views
Canonical way of coloring graphs (individualization) for isomorphism purpose
Stefan Kratsch and Pascal Schweitzer in their paper
Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs
give a characterization of graphs on which
Graph Isomorphism ...
1
vote
0answers
149 views
How does one sample uniformly at random from an uncountably infinite set?
I want to know if there are any examples of polynomial time algorithms which can sample uniformly at random from a given uncountably infinite set? (assuming it is possible)
Does it help if the sample ...
10
votes
0answers
157 views
Hardness in P: methods to show optimality of $O(m^2n)$-like time?
In recent years, there has been exciting work in proving lower bounds for polynomial-time problems conditional on conjectures like SETH or "All-Pairs-Shortest-Paths (APSP) cannot be solved in $O(|V|^{...
8
votes
5answers
294 views
Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)
What are some examples of problems with quasi-polynomial time ($QP$) algorithms that could conceivably be in $P$. In other words, they are in $QP$ for no obvious reason other than no one has found a ...
21
votes
6answers
2k 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 ...
8
votes
1answer
348 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 ...
1
vote
0answers
69 views
Multicuts (or multiway cuts) for 3 Terminals of Minimum Capacity
For each fixed $k \geq 3$, the following well-known problem is NP-complete.
k-Multicut (aka "Multiway Cut", "k-Way Cut", "Multicut")
Input: $(N,l)$ where $N=(V,E,T,c)$ is an undirected $k$-terminal ...
15
votes
2answers
820 views
Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
The $k$-cycle problem is as follows:
Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges.
Question: Does there exist a (proper) $k$-cycle in $G$?
Background: For any ...
3
votes
1answer
202 views
Polynomial-time reductions between undecidable languages
The Turing degree $\mathbf{0}'$ is defined as
all languages Turing-equivalent to the halting problem.
In fact any recursively enumerable language is
polynomial-time reducible to the halting problem.
...
21
votes
1answer
815 views
Time complexity with irrational exponent?
Is there any natural problem in P for which the best known running time bound is of the form $O(n^\alpha)$, where $\alpha$ is an irrational constant?
