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.

1
vote
1answer
157 views

Is polynomial time reducibility reversible?

If a language $A$ is reducible to some language $B$, does it follow that $B$ is reducible to $A$? My guess is no, it having something to do with the function $f$ in the definition of $A$ reducing to $...
1
vote
2answers
47 views

Time complexity for this simple loop

This is the code: j=2 while j<(n*n) j=j*j At first my approach was to treat this like this loop ...
1
vote
2answers
147 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, ...
1
vote
2answers
3k views

Show that P is closed against the Kleene star

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$. Prove that $L^*\in P$ my approach: I tried to generate a turing machine but I got stuck with the thing of ...
1
vote
1answer
276 views

P-Completeness and Reducibility

I am taking an algorithm analysis class and am stuck on one of my homework problems and would appreciate it if I could receive some guidance. The problem I'm stuck on is proving that the empty ...
1
vote
2answers
371 views

P vs NP: Assuming P = NP

Lets assume $P = NP$. Can we say if every language $L \in P$, then $L \in NPC$? I read $P \subseteq NP$, which means that $L\in NP$. So I know for example, that a language can be $NP \text{ hard}$, ...
1
vote
2answers
93 views

Reduce 4-SAT to 5-SAT

given is a reduction from 4-SAT to 5-SAT. How is it possible to describe such a function? I found some informations about reduction 3-SAT to 4-SAT here, but it can't help me so much.
1
vote
1answer
965 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. ...
1
vote
1answer
70 views

Complexity of general polynomial map evaluation is polynomial?

A polynomial map is equal to another polynomial map iff they take on the same values at each point. So this is different from formal polynomials. So since in $\Bbb{Z}_p$, $x^{p-1} = 1$ for all $x \...
1
vote
1answer
90 views

Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology?

Is the following true or false? Why? Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq_{p} X$.
1
vote
1answer
61 views

Polynomial Complexity (Relative to the Size of the Input)

I came across the following statement: "Since b is smaller than n, the complexity $O((n + mb)^3)$ is polynomial." I suppose it has something to do with the notion of polynomiality in terms of the ...
1
vote
2answers
155 views

$DTIME(f(n)) \subset of DSPACE(f(n))$

I think this is again an easy one: $DTIME(f(n)) \subset DSPACE(f(n))$ They say its trivial but I dont see it, why? And would $DTIME(f(n^2)) \subset DSPACE(f(n^2))$ also be true? if yes why ...
1
vote
2answers
32 views

If a decision problem $A \in \text{NP}$ and there exists reduction so that $A \leq_p B$, for decision problem B, what can be deduced about B?

I think that it implies that B can be solved by a non-deterministic polynomial time or worse Turing machine, but I realise that there is possibly some greater result that I'm missing. Thanks in ...
1
vote
1answer
84 views

Polynomial time problems with provably high degree time complexity?

For any integer $k$, does there exist a decision problem in $\textbf P$ that can be proven to require $\Omega(n^k)$ steps?
1
vote
1answer
257 views

Is the complement of MAX-CLIQUE in NP?

Let $$MAX-CLIQUE = \{\ <G,k>\ |\ G\ is\ an\ undirected\ graph,\ and\ the\ largest\ clique\ of\ G\ has\ k\ vertices\}$$ Does $MAX-CLIQUE\in coNP$? If it does, can you think of a verifier? ...
1
vote
1answer
50 views

For any non-trivial $A,B$, finding a language which both are polynomially reducible to

Given two non-trivial (not $\emptyset$ or $\Sigma^*$) languages $A$, $B$ over an alphabet $\Sigma$, which of the following is correct: a. There is a language $C$ such that $A\leq_pC$ and $B\...
1
vote
1answer
64 views

P decision problem that potentially requires at least $\Omega(n \log n)$ in the Turing model?

Currently, it is not proven that $NP \geq O(n \log n)$ in the Turing Machine Model. The weakness of this statement can be illustrated by NP-complete problems, which we think require way more time. ...
1
vote
1answer
94 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.
1
vote
1answer
254 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}$?
1
vote
1answer
66 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
vote
1answer
87 views

Polynomial Identity Testing Evaluating a polynomial on a circuit

Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of ...
1
vote
1answer
73 views

Polynomial Time reducible explanation

Have a set of examples given to me, but I'm pretty sure they're all wrong. Can someone verify that my understanding of them is correct? If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X ...
1
vote
1answer
29 views

Determine whether a system of $n$ linear equations has solutions in $\{0, 1\}^n$ in polynomial time

I'm trying to determine whether it is possible to decide if a system of $n$ linear equations with integer coefficients and $n$ variables has a solution in $\{0, 1\}^n$ in polynomial time. ...
1
vote
1answer
78 views

Find Hamiltonian cycle in polynomial time

I want to know for what types of graph it is possible to find Hamiltonian cycle in polynomial time. It would be helpful also to show why on some types of graph finding Hamiltonian cycle would be only ...
1
vote
1answer
147 views

Relation beetween log-space reduction and polynomial time reduction

I read somewhere that given two languages A and B, if A <=(log) B, then A <=(P) B (with <=(log) the log-space reduction and <=(P) the polynomial time reduction), but I'm not sure about the ...
1
vote
2answers
101 views

NP Class Definition of a Certificate

Given the definition for all x ∈ Σ∗ x ∈ L ⇔ ∃ u ∈ Σ∗ with |u| ≤ p(|x|) and M(x, u) = 1 Lets say the input x = ababab Then the certificate u shouldn't be longer than p(|x|). But what would be p(|...
1
vote
1answer
25 views

How to prove that $n^d$ is $O(b^n)$ from $n$ is $O(2^n)$, given that $d>0, b>1$? [duplicate]

I'm reading Rosen's Discrete Mathematics and Its Application, at Page 212, it's about the "Big-O" notation using in computer science. This is the description in the book: And here is my reasoning: ...
1
vote
1answer
209 views

Poly-time reduction is not antisymmetric

Lemma. (Transitivity) "$\leq_p$" is a transitive relation on languages, i.e., if $L_1 \leq_p L_2$ and $L_2 \leq_p L_3$, then $L_1 \leq_p L_3$. Proof. By definition, there are poly-time functions $...
1
vote
1answer
326 views

What is the precise definition of pseudo-polynomial time (feat. Counting Sort)

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
1
vote
1answer
50 views

If the difference between two oracles is negligible, is the difference between a PPT algorithm with these two oracles also negligible?

We say a negligible function is a function $\epsilon(n):\mathbb{N}\rightarrow \mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $n > N_c$, $$\...
1
vote
1answer
58 views

For which level of PH is $\operatorname{VALID}$ complete

I have the decision problem $\operatorname{VALID}$ which is the set of all valid propositional formulas (tautologies), I know that $$\overline{\operatorname{SAT}}\equiv_m^p \operatorname{VALID}.$$ ...
1
vote
1answer
505 views

reducing $CLIQUE$ from decision to search problem

consider the language:$$CLIQUE = \left\{\langle G,k\rangle \ |\ \text{ $G$ is a graph containing a clique of size at least $k$ } \right\}$$ Suppose there's a polynomial time algorithm for $CLIQUE$. ...
1
vote
1answer
374 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 ...
1
vote
1answer
47 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)...
1
vote
1answer
82 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$...
1
vote
1answer
50 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 ...
1
vote
1answer
58 views

Is P closed under subwords? [closed]

Given a language $L\subseteq \Sigma^*$ in $P$, is the language $subwords(L) = \{v\in\Sigma^* : \text{there exist } u,w\in \Sigma^* \text{ with } uvw\in L\}$ that consists of all subwords of words ...
1
vote
1answer
505 views

What's the difference between “polynomial time Turing-reducible” and “polynomial time many-to-one reducible”? [duplicate]

The following definitions are from Li, M., & Vitányi, P. (1997). An introduction to Kolmogorov complexity and its applications (2nd ed.), pg. 38. A language $A$ is called polynomial time Turing-...
1
vote
0answers
36 views

Smallest string containing sets of letters

I am looking for a solution to this problem: Given multiple sets of letters (Set0={a,b,c,d}, Set1={d,e,f,g}, Set2={a,b,e,g}, ...), what is the minimal length of the string containing all the sets. The ...
1
vote
0answers
99 views

CRC computation speed vs polynomials features

I tried to find information about how features of a CRC polynomials influence computation speed of implementations. It is obvious that (depending from the CPU architecture the algorithm runs on) ...
1
vote
0answers
44 views

Finding simple min-weight path between two vertices in graph with negative edge weights

Given a weighted graph (negative weights are allowed) and two vertices $u$ and $v$, can we find the simple min-weight path between $u$ and $v$? There can be a negative cycle on the path from $u$ to $v$...
1
vote
0answers
14 views

Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
1
vote
1answer
29 views

polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$

If we have two languages $L_{1} \subseteq \Sigma^{\ast}_{1}$ and $L_{2} \subseteq \Sigma^{\ast}_{2}$ I proved that when $L_{2} \in \textbf{P}$ and $L_{1} \leq_{p} L_{2}$ then $L_{1} \in \textbf{P}$ ...
1
vote
1answer
106 views

Show that the SAT Problem for CNF formulas with at most two occurences of each variable can be solved in polynomial time

Assuming, I have an arbitrary CNF Formula in which each variable has at most two occurences, how can I proof/show that this can be solved in polynomial time? My first thoughts so far: because each ...
1
vote
0answers
77 views

Must every NP-Complete Problem have a class of instances which is solvable in Poly time? [closed]

Is there any theorem that states that any NP-Complete Problem has a class of instances solvable in Poly time? For example, some problems like vertex cover are NP-Complete on general graphs but can be ...
1
vote
3answers
2k views

What are the implications of P=NP? [duplicate]

Is there a list of implications of $P=NP$? Presumably, a proof of $P \ne NP$ will be by contradiction, for which a list of consequences of $P=NP$ would be useful.
1
vote
0answers
93 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 ...
1
vote
0answers
34 views

Pedagogic reference on cut generating functions

Can you recommend an introduction to the topic of cut generating functions? I am looking for introductory or review-like material. I did find the following survey paper, but it seems to be addressed ...
1
vote
0answers
33 views

Besides practical computing applications, is there a reason polynomial is “good” and exponential is “bad”? [duplicate]

The overarching theme of computer science seems to be that polynomial time or space or what-have-you for an algorithm is a success, and exponential is a failure. The definitions of P and NP revolve ...
1
vote
0answers
81 views

Suppose P = NC - what then? [duplicate]

Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?