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.

Filter by
Sorted by
Tagged with
0
votes
2answers
837 views

How can I prove that there is a decidable language which is not in P?

Generally, I want to use the diagonal argument to prove it. I tried to define a language $A$ which is constructed by a Turing machine $D$: It will only take a input which has a form of a ...
1
vote
1answer
588 views

relation between ntime and dtime

Given DTIME($n^2$) contains NTIME($n^{100}$) show that P=NP. I think it's supposed to be straightforward but I just can't see it. Take $L$, a language in NP. $L$ has a Turing machine which runs in ...
8
votes
2answers
1k views

Any problem solved by a finite automaton is in P

After my Theory of Computation class today this question popped in my mind: If a problem can be solved by a finite automaton, this problem belongs to P. I think its true, since automata recognize ...
0
votes
1answer
121 views

Detemine if two DFA's are non-disjoint in polynomial time?

Given two DFA's , $M_1$ and $M_2$, I want to create an algorithm that determines if their languages are disjoint or not. The algorithm will run in polynomial time. My idea is this: Let's say WLOG ...
6
votes
2answers
286 views

Does P=NP imply polynomial solutions to #P?

Is it true that $\#P$-complete problems could possibly be solved in polynomial time if P=NP? I know that even some counting problems related to polynomial time decision problems are $\#P$-complete, so ...
4
votes
0answers
140 views

Time complexity of languages recognized by linear bounded automata with restricted number of writes

Suppose that $L$ is a language recognized by a linear-bounded automaton with the constraint that it can only change each of its input cells at most $t$ times each, where $t$ is some constant integer. ...
3
votes
2answers
846 views

Solve parity game in polynomial time?

Is it possible to solve a parity game in polynomial time? If yes, how? If no, why not?
1
vote
2answers
204 views

What is the name for polynomially solvable optimisation problems?

An optimisation problem that allows to solve a NPC decision problem through a polynomial reduction is called NP-hard. For these optimisation problems no polynomial algorithm is known. Symmetrically, ...
4
votes
1answer
2k views

Does two languages being in P imply reduction to each other?

Given two languages $L_1$ and $L_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how? I noticed that if $L_1$ is the ...
1
vote
1answer
116 views

How could I prove that $B$ reduces to $A$ in polynomial time in this case?

Let $A$ be a decision problem with at least one yes instance and at least one no instance. Also let $B \in \textbf{P}$. How could I prove that B reduces to A in polynomial time? Thanks in advance.
4
votes
1answer
127 views

Is every language in PTime also context-sensitive?

Context-sensitive languages are exactly those that can be recognised using linearly bounded automata, i.e., those in NSPACE(O($n$)). This subsumes all languages that can be recognised in linear time, ...
1
vote
1answer
1k views

How to prove an polynomial run time is faster than exponential using definition of big O

This is for homework so feel free to not give me an answer but steer me in the right direction. The problem states: Prove that $n^{1000000} = O(1.000001^n)$ using the formal definition of Big-O. ...
2
votes
1answer
176 views

Are finite-domain binary constraint satisfaction problems solvable in polynomial time?

Suppose a CSP has $n$ variables with finite domains of maximal size $d$. Furthermore, all constraints on the variables are binary. Can such a CSP be solved in polynomial time in $n$ and $d$? This was ...
4
votes
1answer
290 views

Simulate NPDAs with DTMs using only polynomial overhead

We know by polynomial-time parsing algorithms like the classical CYK algorithm that $\mathrm{CFL} \subseteq \mathrm{P}$. Furthermore, it is easy to show by direct simulation that $\mathrm{DCFL} \...
0
votes
1answer
113 views

Time complexity of the fastest algorithm for this case

An array of $n$ distinct elements is said to be un-sorted if for every index $i$ such that $2≤i≤n−1$, either $A[i] > max \{A [i-1], A[i+1]\}$, or$A[i] < min \{A[i-1], A[i+1]\}$. What is the ...
1
vote
1answer
48 views

On different characterizations of $\mathsf P$

In here it was clarified that $\cap_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})\subsetneq\cap_{\epsilon>0}\mathcal C(n^{n^\epsilon})$ where $\mathcal C(t(n))$ is the class of problems solvable in $O(t(n)...
12
votes
1answer
2k views

Does linear programming admit a strongly polynomial-time algorithm?

The linear programming problem: find a strongly-polynomial time algorithm which for given matrix A ∈ Rm×n and b ∈ Rm decides whether there exists x ∈ Rn with Ax ≥ b. I know that Steve Smale's lists ...
2
votes
1answer
105 views

Reduce $SAT$ to $3SAT$

I was reading this that details a polynomial reduction from $SAT$ to $3SAT$. In case $k = 1$ or $k = 2$, why don't we just replace those clauses with $C_i' = \{{z_1, y_{i, 1}, y_{i, 2}}\}$ and $C_i' =...
4
votes
2answers
254 views

“P may collapse” vs. Time hierarchy theorem

https://en.wikipedia.org/wiki/P_versus_NP_problem states: If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level. They further state that this may be ...
1
vote
1answer
84 views

2-clause satisfiability associated graph

A 2-clause is a clause with at most two propositions (clauses?) : $(p \wedge q,\neg p \wedge q, \neg p,...)$. I have to show that the folllowing problem is $\in$ P: 2-SAT: Input : A conjunction $\Phi$...
0
votes
1answer
168 views

Is the MinMax/optimization/search variant of a decision problem always easier/equal?

Is the MinMax/optimization/search variant of a decision problem always easier/equal in complexity because we can always reduce them to their decision variant? From Wikipedia: If the longest path ...
3
votes
1answer
70 views

Partitioning a bipartite graph to get disjoint components of same size

I have a bipartite graph $G = (V, E)$ where $V = S \cup T$ is the division into the two halves. I want to select $n$ elements from $S$ and $nk$ elements from $T$ such that the graph they generate has $...
1
vote
0answers
98 views

What are widely-used, practical applications to come from the study #P problems?

When, beyond theoretical exercises, do we care how many solutions we can find for something? I had an analogous question for TMs before - why is it useful to study machines that can only deliver ...
2
votes
2answers
580 views

Do problems in P have a minimum number of YES and NO instances?

If a decision problem A belongs to the polynomial complexity class P, must there be at least one YES instance and one NO instance of the problem? I know that in the definition of a Turing machine an ...
2
votes
1answer
799 views

Why isn't TQBF part of the polynomial hierarchy?

TQBF consists of alternating quantifiers, so does $\Sigma^2_n$ for fixed $n$. So given a formula in TQBF, shouldn't there be a level of the polynomial hierarchy that solves it? I think this is ...
12
votes
3answers
2k views

Problems conjectured but not proven to be easy

We have many problems, like factorization, that are strongly conjectured, but not proven, to be outside P. Are there any questions with the opposite property, namely, that they are strongly ...
2
votes
0answers
52 views

Longest cycle, existance of approximate algorithm implies existence of better one

This is an exercise from an old exam that I don't know how to solve. For any undirected graph $G$, let $c(G)$ be the length of the longest (simple) cycle in $G$. Show that if there exists a ...
1
vote
1answer
62 views

How to reduce constrained proofs to 0-1 IP

Consider the following problem: Can $X$ be proven in fewer than $Y$ steps, from axioms $Z$, with finitely many transition rules $\tau$? This lies in $NP$, since if I supply a proof $M$, and ...
2
votes
1answer
553 views

On maximum independent set of line graphs

Are there any special algorithms for maximum independent set of line graphs? Could this special case be in $\mathsf{P}$?
2
votes
1answer
70 views

Is there an example of an oracle A such that P = NP but $\mathsf{P}^A\neq\mathsf{NP}^A$?

The question is stated in the title, I would like to see a counter example if there is any. Thanks.
0
votes
0answers
53 views

Polynomial Reduction and P [duplicate]

Why w ∈ A if and only if f(w) ∈ B ? Which the signification of "if and only if" ?
0
votes
1answer
1k views

If the Clique-k Problem is in P, why not Clique as well?

I have looked at the other answers to this but I still don't get it. (for instance: Why is the clique problem NP-complete?) The general clique problem is defined as $\text{CLIQUE} = \left\{ (G, k) | ...
2
votes
1answer
49 views

Shorten Length Reduction

I've stumbled upon this Question: We say that a reduction $f$ of a language $A$ to a language $B$ is a Shorten length reduction, if there exists a number $ n\in N $ s.t for every $ w\in A $, s.t ...
0
votes
1answer
508 views

What is an example for a decidable language not in P?

I'm having trouble showing that $P\neq R$. Obviously $P\subseteq R$, but is there a decidable language which is definitely not (under all answers to open questions s.t. $P=NP$ or $NP=PSPACE$) in $P$ ?...
4
votes
2answers
115 views

Resource bounded reductions for RE-Complete problems

Given that the halting problem is RE-Complete, we can reduce any problem in RE to an instance of the halting problem. Are there are any results on the time-bounds for this reduction? Can we do this ...
3
votes
1answer
291 views

Equality of cardinality of maximum matching and minimum vertex cover in general

I'm preparing for exam and I came across this problem: We say that a graph is König's graph when the sizes of its minimum vertex cover and maximum matching are equal. Find a polynomial time ...
0
votes
0answers
111 views

Are there any RE-complete languages w.r.t. polynomial reduction?

I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L $, meaning a polynomial-time reduction. I've tried to use $L=A_{TM}$ (the accepting problem), but got ...
6
votes
1answer
1k views

How do we know for sure that EXPTIME ≠ P?

I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It ...
2
votes
1answer
147 views

Why is the set of perfect squares in P?

I am reading an article by Cook [1]. In it he writes: The set of perfect squares is in P, since Newton's method can be used to efficiently approximate square roots. I can see how to use Newton's ...
5
votes
1answer
3k views

Are all languages in P?

Are all languages in $\mathbf{P}$? Note: The definitions of all the symbols and functions here follow the document [1]. The following is my attempt to answer the question. Assume that we design a ...
-1
votes
1answer
91 views

How fast can one compute the power of a number?

Let $x \in \mathbb{R}$ and $k \in \mathbb{Z}^+ \cup \{0\}$ then how fast can one compute $x^k$? If $x, k \in \mathbb{Z}$ then I guess this previous discussion already settled that, How many ...
4
votes
1answer
56 views

Maximize function over a set with a transitive and antisymmetric relation

Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$. For any set $S\subseteq X$ define $\Gamma(S)=\left\{y\in S \mid \not \exists x\in S . (x,y)\in\mathcal{R}\...
3
votes
2answers
1k views

Is it true that P is not equal to deterministic linear space complexity class?

I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class? Is there some proof? Or should I find some algorithm which is not ...
5
votes
2answers
200 views

Implicit complexity and interpretation of total languages

In implicit complexity theory we construct languages that characterize what can be computed in various complexity classes. One major result is Bellantoni and Cook where they show that $FP$ can be ...
4
votes
2answers
98 views

On certificates in BPP (avoiding majority vote)

Assume that we have a $BPP$ algorithm $A$ for a problem $\Pi$. Given input $x$ we run $A$ on $\Pi$ polynomially many times and take majority output. However if the problem $\Pi$ is also in $NP$ ...
0
votes
1answer
98 views

Relation of deterministic push down automata and lower elementary recursion

Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata. Deterministic context free languages can be recognized by a ...
2
votes
1answer
52 views

On graph isomorphism over exponential word sizes

Is it known Graph isomorphism can be done in poly time if we allow exponential word sizes? (Shamir's poly time Integer Factoring algorithm is over exponential word sizes).
2
votes
1answer
203 views

Polynomial hierarchy: inclusion between spaces

Using the definition for the polynomial hierarchy: $$ \Sigma_{i+1}^P = NP^{\Sigma_i^P} $$ $$ \Pi_{i+1}^P = coNP^{\Sigma_i^P} $$ I have been asked to to show that: $$ P^{\Pi_k^P } \subseteq \Pi_{k+1}...
1
vote
1answer
75 views

If a CSP (over a finite domain) has only linear inequalities as constraints, is it solvable in linear time?

I have an optimization problem in fuzzy logic that I want to model and solve as a CSP. If I could use only linear inequalities in my encoding, is the resulting CSP solvable in linear time? Problem ...
-1
votes
1answer
58 views

A program for polytime languages

Does their exist a program P[m,s] which always halts and for any polytime language exists an m; possibly incomputable; such that P[m,s] accepts only those strings s which are in the language.