Skip to main content

# 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.

424 questions
Filter by
Sorted by
Tagged with
3 votes
1 answer
55 views

• 13
1 vote
0 answers
29 views

### Inefficient double lengthening PRG [closed]

I'm trying to prove that an inefficient double-lengthening PRG exists, i.e. construct a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$ My current approach is to bound the number of poly-time non-uniform ...
• 141
3 votes
2 answers
875 views

### How to find a satisfying assignment in polynomial time without the use of randomness?

Assume that we are given a formula in 3-CNF such that at least 1% of the complete assignments satisfy it. My question is how to find a satisfying assignment in polynomial time without the use of ...
• 327
3 votes
0 answers
42 views

### Approximation of the Normal Set Basis Problem

Let $B$ and $C$ be collections of finite sets. We say that $B$ is a normal basis of $C$ if for all $c\in C$ there is a pairwise disjoint subcollection of $B$ whose union is exactly $c$. The input of ...
• 2,951
1 vote
1 answer
44 views

### Is it possible to find reductions from problems in $\mathsf{NP}$ to SAT based solely on the certificate verification algorithm?

The following problem has made me ask this question: Given a boolean formula $\varphi(X)$ decide if there exists a quantification of $\varphi(X)$ with $k$ $\forall$ quantifiers that holds true. ...
• 1,684
0 votes
1 answer
67 views

### Is the function $f: \mathbb{N} \rightarrow \mathbb{N}$ where $f(n) = 2^n$ computable in polynomial time using TM?

Assuming that the input $n$ is given as a decimal number. I was asked to prove whether the function $f: \mathbb{N} \rightarrow \mathbb{N}$ where $f(n) = 2^n$ is computable in polynomial time using TM ...
• 275
0 votes
0 answers
28 views

### Is it possible to perform clause-pair minimization on a CNF instance in $o(n^2)$ time?

Let $\varphi(X)$ be a boolean formula in CNF over a set $X$ of boolean variables $x_1,x_2,...,x_n$. Let $c_i$ denote $i^{th}$ clause in $\varphi(X)$. $x_j^0$ denotes $\overline{x_j}$ and $x_j^1$ ...
• 1,684
0 votes
0 answers
51 views

### HAMILTONIAN PATH AND SUBSETSUM

If we were to discover a deterministic algorithm capable of deciding, in polynomial time, whether a given graph contains a Hamiltonian path, would that imply that the problem SUBSETSUM belongs to P? ...
• 1
3 votes
0 answers
82 views

### Subset sum problem with big items

Consider the variant of the Subset Sum problem, where the input is a list of $2 m + 1$ positive integers of sum $2 S$, and the goal is to find a subset with the largest sum that is at most $S$. The ...
• 6,070
0 votes
1 answer
42 views

### Pseudopolynomials and $NP$ problems like $CLIQUE$

Having encountered the concept of "pseudopolynomials", my understanding is that we have to be careful when the input to a problem is a number, that the complexity of the solution should be ...
0 votes
1 answer
24 views

• 243
2 votes
2 answers
83 views

### Role of a variable in problem definition in time complexity

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)$, with $n = |V|$, the ...
1 vote
0 answers
42 views

### Is there any characterisation of problems solvable in $n^2$ time

Basically I am asking if we know necessary and sufficient conditions for a problem to be solvable in, for example, $n^2$ time. Or if not, if there are any theorems on whether or not a broad class of ...
• 121
0 votes
1 answer
20 views

### NP-HARD optimization problem and instance correlation

If an optimization problem A is NP-hard and P≠NP, then does there exist an instance x of A such that no polynomial algorithm provides an optimal solution for x?
0 votes
1 answer
432 views

### Minimum dominating set on trees

I am working on an NP-Complete problem, i.e., the dominating set. Given a graph $G = (V, E)$, a set $S$ is a dominating set if every vertex $v \in V \setminus S$ has at least one neighbor in $S$. I am ...
1 vote
3 answers
53 views

### Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k?

Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k? Is it correct to say that it doesn't exist because clique is ...
0 votes
0 answers
17 views

### Complexity Class of the Problem: Existence of Unsatisfying Interpretations in Boolean Formulas

What is the complexity class of the problem if there exist two different interpretations that do not satisfy a given Boolean formula? I believe the problem of existence of an interpretation that does ...
0 votes
0 answers
47 views

### Why are polynomials a natural measure for easiness of computational problems? [duplicate]

We understand the exponential function to constantly grow, which we consider bad for a problem. By constantly growing I mean the ratio $\frac{f(n+1)}{f(n)}$ never tends to 1, where $f(n)$ is the ...
0 votes
1 answer
89 views

### Showing there exists a polynomial-time algorithm for deciding the existence of a linear classifier

For this question I figure we need to define a system of linear inequalities which I thought could be something like this : a1x1 + a2x2 + ... + anxn ≥ b if (x1, x2, ..., xn) ∈ X a1x1 + a2x2 + ... + ...
1 vote
1 answer
53 views

### Do all P problems reduce to all NPI problems?

It is often said that NP-intermediate problems, such as factoring, graph isomorphism, discrete log, and so on are "harder" than the problems in P. Meaning that they cannot be solved in ...
• 327
2 votes
1 answer
64 views

### Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$

I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages ...
• 153
3 votes
0 answers
138 views

### Are any known problems complete for $P$ under "$O(1)$ reductions?"

The usual many-one reduction involves Turing machines transforming an input, $w$, of some language to an input, $f(w)$, of some other language in polynomial time. (Where $w \in L_1 \iff f(w) \in L_2$)....
• 153
0 votes
0 answers
30 views

### Why doesn't the problem of determining whether a word has the same number of 0's and 1's prove $P \neq L$?

One big problem in complexity theory is $P$ vs $L$. I was just thinking about why this isn't trivial, and I came up with the following example. Of course, it cannot work as a proof as it seems too ...
• 153
-3 votes
1 answer
75 views

### Why is this not a proof of P # NP

Suppose that there is a set of strings such that for each n there is at most one string |w| = n. For any given n there is a 50:50 chance that such a string exists. These string can be arranged in a ...
• 21
1 vote
0 answers
35 views

### Are there any Indicators that this specific Integer Linear Program is solvable in polynomial time

I have a pretty complex problem and I am using a rather complex ILP to solve it. In a special case of the problem the ILP is reduced to the following "simple" ILP. Additionally, I know that ...
• 255
0 votes
1 answer
19 views

### Question about the length of certificate of an polynommial-time verifier

We defined a polynomial-time verifier so that it has certificates of length AT MOST p(|x|) for some fixed polynomial p. Why does it not make a difference to require a certificate $c$ to have EXACLTY ...
0 votes
2 answers
29 views

### Is this definition of the class P correct?

The definition of P is given by the union of all DTIME($n^k$) languages for $k >= 0$, where DTIME($n^k$) is the set of languages for which there exist a TM time-bounded by $T(n) = O(n^k)$. However, ...
-1 votes
2 answers
417 views

### Longest increasing subsequence when a number can be added to all numbers in a subarray

A sequence $(a_1,a_2, \dots, a_n)$ and natural numbers $n$ and $k$ are given. We want to calculate the longest (strictly) increasing subsequence of sequence $(b_1,b_2, \dots, b_n)$ for which there ...
• 47
0 votes
1 answer
48 views

### Does "strongly-polynomial time" implies "polynomial time in the unit-cost model"?

Consider any computational problem in which the inputs are integers. As far as I understand, if the problem has a strongly-polynomial time algorithm, it means that the algorithm uses a polynomial ...
• 6,070
1 vote
1 answer
44 views

### Are there arbitraraly hard worst case problems with polynomial time average case complexity?

For example, are there worst case Decidable(but non primitive recursive or other insane time complexity)problems that have a polynomial average case complexity? If so Are there undecidable worst case ...
• 229
0 votes
2 answers
204 views

### Time complexity of finding the minimum by dynamic programing

How can I calculate the complexity of computing $MD(b)$, where $b=(b_1,b_2,\dots,b_n)$? $$MD(s) = \max(s)-\min(s) + \min(MD(s\setminus\{\max(s)\}), MD(s\setminus\{\min(s)\}))$$ where $s$ is a finite ...
• 47
1 vote
0 answers
26 views

### Determine whether we can pack $(r_1, \dots, r_k)$ copies of the variables $(A_1, \dots, A_k)$ into a string $s$, in time polynomial in $|s|$?

Let $s \in \Sigma^*$ be a finite string over alphabet $\Sigma$. Find all "compressible" substrings of $s$, that is substrings $t \leqslant s$ (notation) such that $t\alpha t \leqslant s$ ...
0 votes
0 answers
52 views

### I would not be able to get my simulation in my life time

I am running a simulation on my computer. I tried to multiply two polynomials $g(x), h(x)\in GF(2)[x]$, with $degree(g(x))= 8165$, and $degree(h(x))=25$. This multiplication took almost $20$ minutes ...
• 101
1 vote
1 answer
65 views

### Semi-bounded probabilistic polynomial-time, is it equal to BPP?

The complexity class $\mathsf{BPP}$ is typically defined as the class of all problems for which: Running an algorithm once takes polynomial time at most. The answer is correct with the probability at ...
• 1,684
2 votes
2 answers
160 views

### How can we show that P is not closed under taking all long prefixes?

Let P be the complexity class of languages decidable by Turing machines running in polynomial time. Say a prefix $s$ of a string $x$ is a long prefix (or an L prefix) if $|s|\ge |x|/2$. For a language ...
1 vote
0 answers
106 views

### Why is the ellipsoid method for linear programming only weakly polynomial time?

I am trying to understand why the ellipsoid method is not a strongly polynomial time algorithm for linear programming. Using wikipedia's definition, an algorithm runs in strongly-polynomial time if: ...
• 111
6 votes
0 answers
186 views

### removing an item from n lists in $O(n^{1-\epsilon})$ amortized time

I have a straightforward task that can be done in $O(n^2)$ time. I'm now wondering if the task can be done in time $O(n^{2-\epsilon})$ if we are allowed to do some pre-processing. The problem exists ...
• 2,521
2 votes
2 answers
287 views

### The class of problems that can be solved efficiently using physical means?

By "physical means", I mean, for example, using water pouring down tubes, or combining chemicals, etc. Basically, using some experiment in the physical world to perform some computation. I'...
• 532
1 vote
1 answer
175 views

### Exact formulation of definition of $NP$, in relation to $R$

One definition for $P$ is the set of all languages that have a deterministic turing machine $M$ s.t. if $x\in A$ the machine accepts in polynomial time and otherwise it rejects, also in polynomial ...
0 votes
1 answer
133 views

### Does a constant time compression algorithm proves that P=NP?

Supposed someone came up with a compression algorithm that doesn't iterate through bytes or anything to compress data, does that proves P=NP? That is, an algorithm that doesn't rely on patterns/...
3 votes
2 answers
1k views

### Determining if an NFA accepts an infinite language in polynomial time

Can we determine in polynomial time if the language accepted by an NFA is infinite? The case of DFA is simple, but converting an NFA to a DFA may take exponential time. Also, I ran into this post, ...
• 339
1 vote
1 answer
69 views

### Proving 2SAT is in P vs algorithm for finding a satisfying assignment

I want to understand the proof in the following link that 2SAT is in P. What is the need for the last corollary? Wouldn't be enough to just prove the case for the graph with the help of the path ...
• 113