2022 Developer Survey is open! Take survey.

Questions tagged [polynomial-time]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-1 votes
1 answer
63 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 ...
user avatar
  • 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(...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
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$?
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
13 votes
0 answers
337 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 ...
user avatar
1 vote
1 answer
127 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$ ...
user avatar
  • 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 (...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
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 ...
user avatar
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{...
user avatar
10 votes
2 answers
343 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
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$...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
  • 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 ...
user avatar
  • 748
10 votes
1 answer
215 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
13 votes
1 answer
734 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. ...
user avatar
  • 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 ...
user avatar
  • 12.5k
5 votes
2 answers
392 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$ ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 705