Questions tagged [polynomial-time]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
147 views

list of 3-CNF formula that can be solved in polynomial time

Suppose i want to program a 3-SAT solver. I want my solver to first check whether a formula is in the list of 3-CNF that currently known can be solved in polynomial time before resorting to brute ...
  • 101
0 votes
1 answer
108 views

Can one find any solution to this matrix problem in polynomial time?

I am given an M * N (M > 1, N > 1) matrix with all the numbers blackened but their row and column sums are visible. For example, I am given this 3 * 3 matrix. And one of the possible matrix ...
0 votes
2 answers
337 views

Solving 3-SAT in O(n^6)?

There's an algorithm (published on GitHub) which is claimed to solve any 3-SAT formulation in polynomial time with a complexity of max O(n^6). I would usually brush claims like this away, but having ...
  • 77
0 votes
0 answers
45 views

Are the Eigendecomposition and Singular Value Decompositions in the class P?

I can run, for instance, np.linalg.eig or np.linalg.svd on my computer in polynomial time. However, my understanding is that if the intermediate steps require too many bits to express and give NaNs or ...
3 votes
1 answer
102 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 ...
2 votes
0 answers
70 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 ...
5 votes
0 answers
107 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
55 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
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 ...
  • 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(...
1 vote
1 answer
115 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
181 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
155 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 ...
2 votes
0 answers
210 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
118 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
257 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 ...
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 ...
1 vote
1 answer
133 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
140 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
106 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
0 answers
218 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 ...
8 votes
1 answer
417 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
2 answers
357 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
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
68 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
332 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
1 answer
155 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
1 answer
272 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, ...
's user avatar
3 votes
0 answers
122 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
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
171 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
199 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
3 answers
773 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
0 answers
139 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
187 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
1 answer
186 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
219 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
1 answer
335 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
0 answers
121 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
0 answers
125 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
0 answers
382 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
244 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 ...
13 votes
1 answer
751 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
338 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