Questions tagged [polynomial-time]
The polynomial-time tag has no usage guidance.
102
questions
3
votes
1
answer
93
views
Efficient transformation into CNF preserving entailment
Suppose you have two propositional formulas $\varphi$ and $\psi$, not necessarily in CNF. I want to convert them to 3CNF efficiently (hence introducing auxiliary variables) in such a way that $\varphi ...
- 419
2
votes
0
answers
67
views
Prize Box Ordering Problem With Position Constraints: Easy or Hard
I have a problem where we have $n$ boxes, each box $i$ have probability $p_i$ of containing a prize with value $h_i > 0$, and remaining probability of containing nothing. Now we are asked to order ...
- 43
5
votes
0
answers
105
views
Joint Scheduling Problem with Variables Arrival Times
The scheduling problem $1\bigl|r_j\bigl|\Sigma\,U_j$ is strongly NP-hard but when preemption is allowed the scheduling problem $1\bigl|pmtn,r_j\bigl|\Sigma\,U_j$ becomes strongly polynomial.
I have a ...
- 325
2
votes
0
answers
54
views
Is there a poly-time algorithm to compute the drawing of a simple graph (need not be planar) in a 2D-plane such that any two edges cross at most once?
Does there exists a ploynomial time algorithm to embed a simple graph(need not be planar) in a plane satisfying the following conditions?
No edge touches vertices other than its end vertices.
At any ...
-1
votes
1
answer
62
views
Interpolation to find polynomial multivariate derivative
This question came when reading a paper here about affine projections of polynomials.
The publisher claims in Proposition 22 that
Let $f(\mathbf{x}) \in F[\mathbf{x}]$ be an $n$-variate polynomial of ...
- 101
1
vote
0
answers
29
views
How to deal with the time to minimize a function in a given interval?
I'm writing a paper in which I designed an algorithm running in $O(n^2m)\cdot T(f)$ to solve my problem, where $n,m$ is the size of input and $f:\mathbb{R}\rightarrow \mathbb{R}$ is a function, and $T(...
- 451
1
vote
1
answer
110
views
3-SAT runtime if an optimal order to eliminate possible solutions is known
As a mental exercise I have been playing around with the 3-SAT problem, but I am having difficulty proving or disproving the usefulness of a current idea that I am playing around with.
My current ...
1
vote
1
answer
178
views
Young Diagrams and distinguishing between two distributions
Introduction:
The reference for everything is this paper.
The Robinson–Schensted–Knuth (RSK) algorithm is a well-known
combinatorial algorithm with diverse applications throughout
mathematics, ...
- 153
1
vote
0
answers
153
views
Is polynomial-time the same in all classical computational models?
There are many models of computability, all giving the same notion of 'computable function'. To pick a few examples:
Turing machines (with variants: one-ended, two-ended, multiple tapes...)
RAM ...
- 119
2
votes
0
answers
206
views
Simultaneous evidence for $L\neq NL$ and $P\neq NP$
We believe $L\neq NL$ and $P\neq NP$.
Is there any evidence which simultaneously imply $L\neq NL$ and $P\neq NP$?
- 12.5k
0
votes
0
answers
115
views
$\mathsf{ACC}^0$ and $\mathsf{TC}^0$ with $\mathsf{Cuniform}$-$\oplus\mathsf{L}$ or $\mathsf{Cuniform}$-$\mathsf{NC}^1$ oracle?
$\mathsf{TC}^0$ is a small class with $\oplus\mathsf{L}$ containing it.
Following inclusions are known:
$$\mathsf{Cuniform}\mbox{ -}\mathsf{ACC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\mathsf{TC}^0\...
- 12.5k
5
votes
2
answers
253
views
Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?
Since $e$ is transcendental, the function $f:\mathbb Z_{\geq 0}^{n+1}\to \mathbb R$ is injective,
$$ f(\underset{\text{Integers}\ \geq\ 0}{\underbrace{a_0,a_1,\ldots, a_n}}) = a_0 + a_1e+a_2e^2+\cdots ...
- 1,679
13
votes
0
answers
336
views
NP-hardness for one-dimensional facility location problem with entrance fee for each customer [closed]
We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
- 89
1
vote
1
answer
126
views
Complexity of a satisfiability problem
I would like the know the complexity of a specific satisfiability problem. I have a feeling it could be solved in polynomial time, but I am not sure about it. The problem is described below.
Given $n$ ...
- 13
3
votes
0
answers
91
views
Are there enumerations of machines for all languages in 𝑃 such that there exists a simulator that can efficiently run all the machines enumerated?
From Kozen INDEXINGS OF SUBRECURSIVE CLASSES: "the class of polynomial time computable functions is often indexed by Turing machines with polynomial time counters.... The collection of all (...
- 39
-4
votes
1
answer
138
views
Is there an algorithm for 3x3 sudokus without backtracking? [closed]
From what I can see on Wikipedia and the Internet at large, all sudoku solving algorithms (including human ones) employ some kind of EXPTIME backtracking search for some sudokus.
Are there any SAT ...
- 183
-2
votes
1
answer
1k
views
Sequential vs Distributed algo question
If a certain graph problem in the $\textbf{sequential}$ setting is proven to have "no" better constant-factor approximation algorithm than say a 2-approx. algorithm in polynomial time, then does this ...
- 9
1
vote
1
answer
105
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 \...
- 219
10
votes
0
answers
214
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 ...
- 1,519
8
votes
1
answer
402
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{...
- 1,519
10
votes
2
answers
342
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 ...
- 10.7k
0
votes
0
answers
60
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,443
1
vote
0
answers
107
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 ...
- 21
2
votes
0
answers
66
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 ...
- 633
8
votes
0
answers
325
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 ...
- 181
4
votes
1
answer
154
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 ...
- 600
10
votes
1
answer
268
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, ...
user17918
3
votes
0
answers
118
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$...
- 4,900
7
votes
1
answer
161
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 ...
- 300
5
votes
1
answer
170
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 ...
- 12.5k
4
votes
1
answer
193
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 ...
- 71
8
votes
3
answers
734
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$ ...
- 4,900
0
votes
0
answers
138
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 ...
- 12.5k
1
vote
1
answer
184
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 ...
- 119
3
votes
1
answer
173
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$ ...
- 12.5k
4
votes
0
answers
144
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 ...
- 748
10
votes
1
answer
214
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 ...
- 4,900
14
votes
1
answer
328
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
...
- 4,900
2
votes
0
answers
116
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,519
1
vote
0
answers
122
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, ...
- 11
5
votes
0
answers
380
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 ...
- 151
6
votes
1
answer
241
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 ...
- 558
13
votes
2
answers
1k
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, ...
- 230
7
votes
1
answer
262
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 ...
- 233
13
votes
1
answer
733
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.
...
- 780
7
votes
0
answers
329
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 ...
- 12.5k
5
votes
2
answers
391
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$ ...
- 12.5k
10
votes
1
answer
259
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-...
- 454
-2
votes
1
answer
242
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 graphs can ...
- 10.8k
1
vote
1
answer
996
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 ...
- 705