All Questions
Tagged with complexity-theory polynomial-time
225 questions
0
votes
1
answer
31
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, ...
0
votes
2
answers
58
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
228
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
43
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,919
0
votes
0
answers
48
views
Encapsulated linear memory of Turing Machine
A function $f$ is said to be thinking in an encapsulated linear memory if:
$f(x)$ is a polynomial block (that is, there exists a polynomial $q$ so that $|f(x)|\leq q(|x|)$) for each input $x$.
...
- 25
1
vote
1
answer
36
views
self-reducible in NP-time
We say that a language 𝐿 is 𝑘-self-reducible if there exists a function 𝑓 such that:
𝑓 is computable in polynomial time, and
There exists $𝑛_0 ∈ ℕ$ such that for all 𝑥 of length at least $𝑛_0$...
user150715
1
vote
2
answers
63
views
UNIQUE-PATH in P assuming LPATH is in P
We define the following languages:
LPATH = {<G, a, b, k>|G is an undirected graph that contains a simple path of length at least k from a to b}.
UNIQUE-PATH = {<G, a, b>| G is an ...
- 141
2
votes
2
answers
63
views
In class P, does decidability implies searchability?
I'm studying a course on Intro to Computability, and I couldn't find an answer.
Often, we refer to problems in $\text{P}$ as problems that we can "efficiently search a solution for" (where ...
- 21
1
vote
0
answers
18
views
What is the computational complexity of finding the splitting field of a polynomial?
Suppose $K$ is a number field and $f \in K[x]$ is irreducible. What is the computational complexity of computing f.splitting_field()? I'm also interested in the ...
- 133
16
votes
2
answers
2k
views
What is so fundamental about polynomial functions that they are used to demarcate the Hardness boundary in NP complexity classes?
This question has been bugging me ever since I first came across the concept of NP, NP-Complete, and NP-Hard a few years back: what is so fundamental about the polynomial functions that they are used ...
- 261
6
votes
0
answers
112
views
Polynomial time algorithms for graphs and cycles
For a given undirected graph $G$ , let $ c(G) $ denote the length of the longest cycle in $ G $ (by cycle, we mean a closed path without repetitions). Prove that if there exists a polynomial-time ...
- 61
3
votes
1
answer
71
views
Cover a set of points using subintervals of a list of intervals
Given a set of points $\{p_1, p_2, \dots p_n\}$ and a set of intervals $I =\{[a_1, b_1], \dots [a_m, b_m]\}$, you are asked to find a set of subintervals $S = \{[c_1, d_1], \dots [c_m, d_m]\}$ where $[...
- 161
1
vote
1
answer
101
views
Polynomial solutions, one less
Let $L$ be a language in the class $FP$ of all polynomial-time solvable problems.
The class $FP$ is defined by having a TM $M$ s.t. for any $x$ it computes in polynomial time a $y$ s.t. $(x,y)\in L$. ...
- 534
1
vote
1
answer
93
views
Deciding if a regular language is empty can be done in polytime but deciding if it does not accept {0,1}* is not?
In my class we have discussed the fact that, given a representation $\langle R\rangle$ of a regular expression $R$, we can decide whether it accepts any string by first finding an equivalent NFA, and ...
- 377
0
votes
1
answer
47
views
If $P=NP$, then $LCP \in P$
I want to prove that if we assume $P=NP$, then we can find the longest cycle (maximal number of vertices, no repeated edges, only repeated vertex is the starting one) in an undirected graph in ...
1
vote
1
answer
49
views
Why is naive primality test not polynomial, while graph traversal is?
I am reading Sipser's Introduction to the Theory of Computation, and have trouble understanding the difference between polynomial and non-polynomial problems. When describing a PATH problem, where
...
- 11
2
votes
1
answer
47
views
I am struggling to define the space complexity of a turing machine
I have a problem where I have a class A which is made up of problems which is solveable with a TM with space complexity O(logn). I now need to prove that the problem, where an input string of length n ...
- 21
1
vote
1
answer
30
views
Is the set of languages with verifiers running in polynomial time equal to the set of languages decidable by an NTM running in polynomial time?
I have seen two definitions for the set $NP$. One is that it is the set of languages decidable by a nondeterministic Turing machine (NTM) running in polynomial time, and the other is that it is the ...
1
vote
1
answer
87
views
Is this intersection set problem NP-Hard?
Suppose we have collection of n sets $S_1, S_2, \dots, S_n$. Each set has a size of at least $k$. We know for sure that $\exists k$ sets where all of them contain the same $k$ elements; $|S_1 \cap S_2 ...
- 13
0
votes
1
answer
22
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?
1
vote
3
answers
54
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 ...
- 1
0
votes
0
answers
49
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 ...
- 135
0
votes
1
answer
95
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 + ... + ...
2
votes
1
answer
69
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 ...
- 163
4
votes
0
answers
140
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$)....
- 163
0
votes
0
answers
31
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 ...
- 163
-3
votes
1
answer
78
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
0
votes
2
answers
32
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
vote
1
answer
69
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 ...
- 2,041
2
votes
2
answers
168
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 ...
- 305
1
vote
0
answers
122
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
2
votes
2
answers
293
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'...
- 542
1
vote
1
answer
203
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 ...
- 142
0
votes
1
answer
149
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/...
1
vote
1
answer
70
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
1
vote
0
answers
33
views
Prove that CorrectConnSolver is coNP-Complete
I need to prove that CorrectConnSolver is coNP-Complete where CorrectConnSolver is defind as follows:
CorrectConnSolve$= \{C | C(G) = 1 \iff G$ is connected$\}$.
In other words, the
...
- 23
1
vote
1
answer
64
views
How to prove that if Eternal Vertex Cover is Polynomial it's possible to detect its vertices and edges
EVG is defined as EVC = { <G,m,k>| G is an undirected graph and there is as et of m edges in G that are covered by at most k nodes}
If EVG was decidable in polynomial time how could we find the ...
- 165
0
votes
0
answers
95
views
If P = NP then EXP^P = NEXP^NP?
I believe that if P = NP, then that would imply EXP = NEXP (because of the padding argument), and then EXP^P = NEXP^NP (we could replace EXP with NEXP since they are equal, and replace P with NP, ...
- 145
1
vote
1
answer
116
views
Encoding Turing machine-like behavior using families of sequences of vector spaces and modules. P=NP related
Let $F$ be a field. Suppose we have a machine $T$ that works with words that are elements of $F$, for exmaple $F = \Bbb{Z}/2, \Bbb{Q}$ (using arbitrary precision arithmetic), or $\Bbb{Z}/p$ for a ...
- 548
3
votes
1
answer
69
views
Circuit size of a random two to one function
Consider the set of all possible two-to-one functions that map inputs from $\{0, 1\}^{n}$ (domain) to outputs in $\{0, 1\}^{m}$ (co-domain) and let $m > n$.
If I pick a function randomly from this ...
- 249
1
vote
1
answer
596
views
Why is SET PACKING in NP?
I have seen an lot of proves why SET PACKING is NP complete. However, in every prove it states that SET PACKING is clearly in NP. It might be a stupid question, but is not so clear to me. I see that ...
- 13
2
votes
1
answer
353
views
Reducing a CNF formula to a DNF formula in less than exponential time
The easy way is by looking at the $\{0,1\}$-table and construct the corresponding DNF formula from that, but this will take $2^n$ time. I want to do it much more efficiently.
My idea is based upon the ...
- 364
32
votes
2
answers
3k
views
Problems that are polynomially "hard" to compute but "easy" to verify
In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the ...
- 462
-2
votes
1
answer
53
views
Need the time complexity of this conditional statement method
My idea of the program is :
Input = n sets
objective function ObjFn equals to O(n^3)
Output = the order of n sets
Steps:
Applying ObjFn to all n sets
Choose the n of the Minimum ObjFn to be ordered ...
- 1
1
vote
1
answer
317
views
Complexity difference of Vertex cover and Vertex coloring regarding parametrized algorithms
I stumbled upon some problem in my understanding of the complexity classes FPT and XP.
According to Wikipedia (and the Book "Parameterized Algorithms") we know the following about the Vertex ...
- 161
0
votes
1
answer
107
views
Subset Sum With Interval Integer Target
Define the subset sum with interval integer target problem (SSIITP) as follows:
SSIITP Input:
A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$.
An integer $T$.
SSIITP Output:
True, if ...
- 269
4
votes
1
answer
813
views
Proofs of reduction of any hard problem
Approach:1 To prove any unknown problem $B$ is NPH then take any known NPH problem $A$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $A$, then ...
- 1
0
votes
1
answer
144
views
If $A\leq_P B$ and $B\in \text{NP}$, is $A\in \text{NP}$?
Let $A\leq_P B$ mean that the language $A$ is polynomial time reducible to $B$. It is a theorem that $A\leq_P B$ and $B\in \text{P}$ then $A\in \text{P}$.
My question is, if $A\leq_P B$ and $B\in \...
- 103
2
votes
1
answer
134
views
Is there a difference between extremely slow growing functions and constants with respect to computable functions?
So let's say we have the function $f(n)$ that gives $k$ such that $k$ is the smallest number that gives a busy beaver function $B$ value from input $k$ that is greater than $n$. Or more succinctly the ...
- 217