Questions tagged [polynomial-time]
Use for algorithms, algorithm-analysis and complexity-theory questions that aim for polynomial running time resp. time complexity. Such questions often are are reference-requests or about runtime-analysis or time-complexity.
445 questions
0
votes
0
answers
102
views
How time increases when removing quantifiers
Let $L$ be a language such that
$x \in L \Leftrightarrow \exists y_1 \in \{0,1\}^{q(n)} \; \forall y_2 \cdots Q_{k(n)}y_{k(n)} \in \{0,1\}^{q(n)} \; T(x,y_1,\cdots,y_k)$
where $|x|=n$; $q,k$ are ...
- 3,433
1
vote
1
answer
222
views
Can we solve Parity Games in polynomial time given this subroutine?
Parity games are simple games played on a graph: https://en.m.wikipedia.org/wiki/Parity_game
Let $A$ be an algorithm that solves the following problem in polynomial time.
Given: A graph $G=(V,E)$ ...
- 55
2
votes
1
answer
553
views
I have a simple proof for NL=P but I can't find the bug in the proof
I have written a proof of the statement $\sf P = NL \neq NP$. However, since the proof for the first part is quite simple, I suspect that it may be incorrect. I would appreciate it if you could help ...
- 563
2
votes
0
answers
79
views
Find the random bits that used by Turing machine
Let $𝐿 ∈ RTIME(𝑛 ^3 )$. That is: There exists a Probabilistic TM that runs in $𝑂(𝑛^3 )$ time, such that for every $𝑥 ∈ \{0,1\}^∗$
$x ∈ L ⟹ Pr[𝑀(𝑥) = 1] ≥ 2/3$
$x ∉ L ⟹ Pr[𝑀(𝑥) = 0] = 1$
I ...
- 121
0
votes
2
answers
150
views
How to deal with the relationship between [algorithms with time complexity $O(n^c)$] and [polynomial-time algorithms]?
As the title says, two direct questions are showed as followed:
Can real-world algorithms with time complexity $O(n^c)$ be treated as polynomial-time algorithms in complexity theory?
How could I ...
- 31
2
votes
1
answer
295
views
Useful definition of PRG for derandomization
The book by Arora and Barak defines $G: \{0,1\}^* \rightarrow \{0,1\}^*$ to be a cryptographically secure PRG if:
$G$ can be computed in polynomial time in input length.
$|G(x)| = l(n)$, where $n=|x|$...
- 3,433
0
votes
1
answer
197
views
Does a Polynomial-Time Algorithm for Graph Coloring Problem proves P = NP?
Recently, I came across a video introducing an algorithm (GAF) that computes the chromatic number of any connected, undirected graph in polynomial time.
So, what impact it has on P = NP?
- 47
0
votes
1
answer
102
views
Is the time complexity of Levenberg-Marquadt algorithm polynomial?
I'm trying to use Scipy's least_squares function and the documentation says that least_squares uses the Levenberg-Marquadt ...
0
votes
2
answers
160
views
Must an algorithm terminate to be in NPTIME?
I recently completed a coursework on PRIMES and time complexity, and I got marked down for something which I think I got right, I wanted to ask here to make sure. Here is the problem and I will talk ...
- 1
1
vote
0
answers
71
views
Considering that we have the LPT greedy algorithm for the partition problem, do we need PTAS's or FPTAS's in practice?
I was reading these notes on approximation algorithms and I stumbled across a PTAS for an optimization version of the partition problem (essentially the Identical-machines scheduling $P_2 \|C_{\...
- 85
0
votes
1
answer
66
views
Is it possible to convert a Boolean Formula to "negative normal form" in polynomial time?
A Boolean formula using only negation $\neg$, AND $\land$ and OR $\lor$ is said
to be in negative normal form if the negation only appears in front of a variable, like this $\neg(x)$.
So for instance, ...
1
vote
0
answers
63
views
Polynomial time approximation on a similar problem to Densest-k-Subgraph
Given a graph $G$ with $n$ vertices. Each vertex has a weight $w_i$. For any subgraph $H$, define a function for each vertex of $H$, $f(v_i)$, to be the average of the weight of $v_i$ and all weights ...
- 111
0
votes
2
answers
128
views
How can one say solving one np-complete problem in polynomial proves that all np-complete problems can be solved in p?
I keep reading that we don’t know if p=np or if p!=np , but what is the basis for this universality?
This question is derived from this statement from the book Introduction to algorithms, third ...
- 1
2
votes
1
answer
284
views
A 2-coloring of a bipartite graph such that one of the partitions contains exactly k vertices
Given the efficient solvability of the $2$-coloring problem in bipartite graphs, I claim that the this problem can be accomplished within polynomial time.
A algorithm for solving this problem involves ...
- 83
0
votes
0
answers
88
views
Is checking GCD in NC or strongly P?
Given two integers $m$ and $n$ computing $\mathsf{GCD}(m,n)$ is not known to be either in $NC$ or in strongly Polynomial time.
Given three integers $m$, $n$ and $g$, is testing $g=\mathsf{GCD}(m,n)$ ...
- 2,957