Questions tagged [polynomial-time]
The polynomial-time tag has no usage guidance.
120
questions
1
vote
0
answers
44
views
Are classes of graphs represented by adjacency matrix ordered structures?
We know that FO[LFP] captures PTIME on the class of ordered structures. However, I have difficulties interpreting this result. From what I understand, it means that, given a constant, finite alphabet $...
4
votes
0
answers
72
views
distinguishments between query complexity of membership oracles and standard time complexity
Many combinatorial optimization problems can be described as follows. We are given a set system $(E,I)$, where $I \subseteq 2^E$ and a weight function $w: E \rightarrow \mathbb{N}$. The goal is to ...
1
vote
0
answers
53
views
Find linear combination with small support
Let $v_1,\dots,v_n$ be a basis of a vector subspace of $\Bbbk^N$, say for $\Bbbk$ a finite field. I would like an algorithm to find a linear combination of the $v_i$'s with small support, i.e. with ...
2
votes
0
answers
69
views
Resource bounded Kolmogorov complexity hardness on average over a non uniform distribution of inputs
$K^{poly}$, as well as other related problems such as $MCSP$, is believed to be hard on average [1, 2] when the input is sampled from a uniform distribution (since otherwise one way functions, pseudo-...
6
votes
1
answer
244
views
Fast algorithms for time bounded Kolmogorov complexity
For a universal Turing machine $U$, the time bounded Kolmogorov complexity of a string $x$ is silmilar to the usual Kolmogorov complexity but limited to programs $p$ running in time at most $t(|x|)$:
$...
7
votes
1
answer
209
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$...
6
votes
2
answers
331
views
What are the consequences of $BPP \neq P$?
I have seen a lot of people assume, $BPP = P$ . But to me, this seems false intuitively.(Though math is not without unintuitive results) And, to my admittedly limited understanding of the topic, the ...
13
votes
1
answer
260
views
Complexity of 1-or-3-in-3-SAT (odd-3-SAT)
Consider a 3-CNF formula $\Phi$, i.e., a conjunction of clauses of 3 literals. I call odd-SAT (or 1-or-3-in-3-SAT) the problem of checking whether there is an assignment of the variables such that ...
-2
votes
1
answer
116
views
Polynomial vs. Exponential Time Complexity [closed]
Does $2^{log_2{n}}$ grow faster than a polynomial? I know that $2^{log_2{n}}$ can be simplified as $n$ but can it be considered as an exponential?
3
votes
1
answer
103
views
Running time analysis of problems with a variable in problem definition
I am a research scholar in the field of algorithms and complexity theory. The problem that I am currently working is the $[1,j]$-domination problem. Given a graph $G = (V, E)$, $n = |V|$, the problem ...
2
votes
0
answers
105
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 ...
1
vote
2
answers
101
views
Is Maximum Independent Set polynomial-time solvable in $(p,1)$-colorable graphs for general $p$?
It is well-known that Maximum Independent Set (MIS) in bipartite graphs is polynomial-time solvable.
What happens if we generalize the input graphs by replacing the vertices in one partite with ...
2
votes
1
answer
242
views
6-regular graph without small 3-regular subgraph
My name is Balchandar Reddy. I am a research scholar and am currently working on graph algorithms. I am looking to find a 6-regular graph that does not have small 3-regular subgraphs. For example, I ...
2
votes
0
answers
118
views
Computing real numbers with Turing Machines
Consider the following decision problem:
Given a two integers $n$ and $k$, decide whether $k=\lfloor n\pi\rfloor$
Question: Is this problem known to be in $P$?
Although this may look like a stupid ...
4
votes
1
answer
172
views
Computation with cellular automata in practice
It is well known that certain cellular automata (CA) are computationally universal, such as Conway's game of life in 2 dimensions or the rule 110 in 1 dimension. As far as I know, they can emulate ...
17
votes
3
answers
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 ...
4
votes
1
answer
185
views
Finding a "typical" path
Consider an undirected graph with two distinguished nodes $u\neq v$. How hard is it to find an $u-v$ path, such that its length is as close to the average $u-v$ path length as possible?
Formally, for ...
-2
votes
1
answer
618
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 ...
2
votes
0
answers
91
views
Is there a natural problem in P but no polynomial time algorithm is known?
Most of the time, a problem is shown to be in P by the construction of a polynomial time algorithm. I wonder if there is a natural problem that was proved in P but no explicit algorithm was known?
I'm ...
0
votes
1
answer
215
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 ...
0
votes
1
answer
114
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 ...
10
votes
3
answers
1k
views
Choosing random permutations in "strict" polynomial time
This question compares "strict" polynomial time, as opposed to "expected" polynomial time.
Let $S = \{1,2,…,n\}$, and let $O$ be an ordering on elements of $S$ (the number of ...
10
votes
5
answers
440
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 ...
3
votes
1
answer
169
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 ...
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 ...
2
votes
0
answers
69
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
66
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 ...
1
vote
0
answers
45
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
167
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
192
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, ...
1
vote
0
answers
164
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 ...
16
votes
0
answers
498
views
a geometric variant of k-medians. NP-hard or in P?
The following problem is a special case of k-medians. Is it NP-hard? Is it in P?
Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$.
Output: a set ...
2
votes
0
answers
213
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$?
4
votes
1
answer
325
views
Complexity of linear programming
It is known that Linear Programming (LP) is P-complete.
I am interested in approximation algorithms for LP.
There are numerous inapproximability results for NP optimization problems,
e.g. it is NP-...
0
votes
0
answers
120
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\...
13
votes
0
answers
361
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 ...
5
votes
2
answers
267
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
vote
1
answer
147
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$ ...
25
votes
7
answers
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 ...
3
votes
0
answers
95
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 (...
-4
votes
1
answer
150
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 ...
-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 ...
1
vote
1
answer
109
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
225
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 ...
9
votes
1
answer
495
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
485
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
86
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 ...
2
votes
0
answers
113
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 ...
9
votes
3
answers
906
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$ ...
2
votes
0
answers
73
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 ...