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
3
votes
2answers
998 views

The exact relation between complexity classes and algorithm complexities [duplicate]

Are all algorithms which have polynomial time complexity belong to P class ? And P class do not have any algorithm which does have not polynomial complexity ? Are all algorithms which have non ...
3
votes
1answer
81 views

Functional problem and verifying solutions

Is there a functional problem for which there is an algorithm that can decide if a solution is a solution or not in polynomial time but we can't find a solution in polynomial time? Let FP be the ...
3
votes
1answer
80 views

Number of equivalence classes in $P$

I am currently taking a course which involves computational complexity. I was told that polynomial equivalence (polynomial time reduction) divides P into exactly 3 equivalent classes, namely $\phi$ , $...
3
votes
1answer
52 views

Constructing an optimal solution to bin packing using a “magical function” $\phi$

I am taking an introductory course in complexity theory, and as an exercise, we were given the following problem. Consider the bin packing problem, with objects of positive (rational) weights $W = \{...
3
votes
1answer
103 views

$m/p$-equivalence holds after union with an arbitrary finite language

Problem 1: Let $A,B$ be languages over some alphabet $\Sigma$, if $A \equiv_m B$, then for every finite language $C$, $A \cup C \equiv_m B \cup C$. Problem 2: Problem 1 but using polynomial time ...
3
votes
1answer
217 views

Methods of turning a decision problem into finding the certificate?

I usually find this in the context of asking about NP-complete problems, but any decision problem works. We start by assuming there's a polynomial time algorithm that gives the yes or no answer. If it'...
3
votes
1answer
96 views

Characterizing the range of a polytime function

Is it true that an infinite language is in P iff it is the range of a length increasing polytime function? I ask because I know that it is a basic result in computability theory that a set is ...
3
votes
1answer
189 views

A variant of the set cover problem: Is that a known problem?

Can this problem be solved in poly time? Input: $S_i \subset \{1,\cdots,n\}$ for $i=1,\cdots, n$. Question: Is it possible to select an $a_i \in S_i$ for each $i=1,\cdots,n$, such that $\{a_1,\...
3
votes
1answer
28 views

Complexity of pattern matching for modus ponens logical conclusions

Is a Turing machine with added the following contant-time operation equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) to a (usual) ...
3
votes
1answer
81 views

$P=PP$ or $P=PSPACE$ vs $VP=VNP$

We do not know if $P=NP$ has an impact on $VP=VNP$ however how about $P=PP$? Is $PP$ and $VNP$ related and would $P=PP$ or $P=PSPACE$ imply $VP=VNP$? Is there a way to show $\#P$ is in $FP^{PP}$?
3
votes
0answers
48 views

Is a “stacked”, “local” version of 3-SAT NP-hard?

In this previous question, I learned that if each variable in a string $C \in 3\text{-SAT}$ appears only "locally", then finding a satisfying assignment is no longer NP-hard. My question below builds ...
3
votes
0answers
130 views

How to find a minimum spanning forest with a constrained number of nodes in each spanning tree?

Consider a weighted undirected acyclic graph consists of m source (root) vertices and n target vertices. The m-spanning tree problem of the graph is defined as that: (1) each of the m spanning trees ...
3
votes
0answers
74 views

How to find m directed paths connecting the maximal number of vertices in an unweighted directed acyclic graph?

Consider an un-weighted directed acyclic graph (DAG) consists of m source (root) vertices and n target vertices. When there is only one source vertex (m=1), the problem to find a directed path ...
3
votes
1answer
744 views

Relation between logspace-uniform circuits and P-uniform circuits

In the book "Computational complexity" of Barak and Arora, on page 112, they state that: Theorem 6.15: A language has logspace-uniform circuits of polynomial size iff it is in P. The proof of this ...
2
votes
2answers
603 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
3answers
3k views

P is contained in NP ∩ Co-NP?

How should I show that ${\sf P}$ is contained in ${\sf NP} \cap {\sf CoNP}$? I.e., all polynomial time solvable problems and their complements are verifiable in polynomial time.
2
votes
1answer
312 views

Understanding definition of NP and co-NP

From some of the texts I read, one definition of NP is: "An equivalent definition of NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine." and that we ...
2
votes
2answers
267 views

Calculating the number of assignments satisfying a general propositional formula

I know, for a disjunctive clause of the form $x_1 \vee ... \vee x_i$, the number of assignments satisfying it is simply $2^i - 1$, but what about for a general formula? Is the number of satisfying ...
2
votes
1answer
284 views

Proving special case of SAT is in P

Let SAT-100 be the following problem: Input: Any boolean logic formula Output: True if there exists a combination of exactly 100 input variables that satisfy the formula. This is the description of ...
2
votes
1answer
254 views

Solving diophantine equations — does having a bound on the size of the solution help?

Let's define the following languages over the alphabet $\Sigma=\{0,1\}$: H10 is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ ...
2
votes
3answers
114 views

Graph cycles on 40 vertices

I'm trying to create an algorithm in polynomial time, that detects wether or not a graph is in a language. The language specifies that a graph is only part of this language if it has a cycle on 40 ...
2
votes
1answer
214 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 $...
2
votes
2answers
230 views

GOTO vs. including line in loop - will it affect efficiency?

Let's say I have an algorithm something like as follows: ...
2
votes
3answers
2k views

If A is in P and B is non-trivial, then A ≤p B [duplicate]

On wikipedia's article on Polynomial-time reduction it states: Every nontrivial decision problem in P (the class of polynomial-time decision problems, where nontrivial means that not every input ...
2
votes
2answers
85 views

Satisfiable CNFs where each clause contains logarithmically many different literals

Studying for my finals in Complexity theory. This question comes up in different variants and it requires to use probability. A side note before, to be more clear: A CNF clause consists of $n$ clauses ...
2
votes
1answer
41 views

How is Hypergraph Isomorphism (HI) reduced to Graph Isomorphism (GI) in polynomial time?

This question states that the problem of Hyper-graph Isomorphism is equivalent to Graph isomorphism. I have not been able to find a description of the reduction so I am wondering how that might work ...
2
votes
1answer
2k 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
203 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 ...
2
votes
1answer
211 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}...
2
votes
1answer
478 views

Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?

According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ...
2
votes
1answer
42 views

Polynomially related encodings

CLRS states that: For some set $I$ of problem instances, we say that two encodings $e_1$ and $e_2$ are polynomially related if there exist two polynomial-time computable functions $f_{12}$ and $f_{...
2
votes
1answer
49 views

Adding the requirement of linear time on infinitely many inputs into the class $P$

Is the following problem computable in polynomial time? Input: $<M_1>$, encoding of a determinstic TM that runs in polynomial time ($L(M_1)\in P$) Output: $<M_2>$, encoding of a ...
2
votes
1answer
1k views

Question about NP problem certificates and P=NP

From my understanding a problem is considered to be in NP time if it can be solved in polynomial time with a non-deterministic Turing machine and verified in polynomial time with a certificate. My ...
2
votes
1answer
604 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
73 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.
2
votes
1answer
54 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
31 views

Is it Polynomial to decide whether any product of input numbers satisfies a boolean expression?

I have an input number c of n bits and its prime factorization. I want to find a divisor of c with certain fixed bits "f". For example: ...
2
votes
1answer
280 views

Proof of P-Hardness by reduction

I want to proof the P-Hardness of a language. Why is it enough to make a reduction-proof from an other, already P-Complete known language?
2
votes
1answer
136 views

Polynomial Hierarchy — polynomial time TM

Consider, for example, the definition for $\Sigma_2^p$ complexity class. $$ x \in L \Leftrightarrow \exists u_1 \forall u_2 \;M(x, u_1, u_2) = 1, $$ where $u_1, u_2 \in \{0,1\}^{p(|x|)}$, for some ...
2
votes
1answer
404 views

Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time?

Given a positively weighted DAG (directed acyclic graph) $D = (V,E)$, can you create a new non-weighted DAG $D'$ by converting each edge with weight $w(e) = x$ into x non-weighted edges and vertices? ...
2
votes
1answer
791 views

How undecidable is it whether a given Turing machine runs in polynomial time?

The proof of Theorem 1 that PTime is not semi-decidable in this recent preprint effectively shows that it is $\mathsf{R}\cup\mathsf{coR}$-hard. The proof itself is similar to undecidability proofs at ...
2
votes
1answer
295 views

Polynomial Time Algorithm for Steiner Tree Problem

I know about Steiner Tree Problem. It is stated as Input to Steiner Tree Problem is a weighted graph G and a subset T of the nodes (called terminal nodes) and goal is to find a minimum weight tree ...
2
votes
1answer
49 views

Are you allowed to change the specifications of a problem when doing reductions?

I'm doing a polynomial time reduction from problem A (known graph problem) to problem B (funky and specific longest path problem). There is a lot of demands on how problem B is supposed to be solved. ...
2
votes
1answer
29 views

Is there a “well known” example of a constraint satisfaction problem on a 3-element set which is polynomial-time solvable?

I'm basically looking for an example (in maybe graph theory) of a constraint satisfaction problem which has a 3-element set as a domain and the problem is known to be polynomial-time solvable.
2
votes
1answer
605 views

Complexity of polynomial interpolation

Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of ...
2
votes
2answers
531 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 ...
2
votes
1answer
661 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 ...
2
votes
1answer
673 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 ...
2
votes
1answer
1k 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 ...
2
votes
1answer
90 views

Polynomial Time Reduction - Does 0 calls to the black box still imply a reduction?

Using the following definition: Reduction: There is a polynomial-time reduction from problem $X$ to problem $Y$ if arbitrary instances of problem $X$ can be solved using: Polynomial ...

1 2
3
4 5
7