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.
406
questions
0
votes
0
answers
18
views
Is PAD(EXP) = P?
Can I say that all languages in the class $\textbf{P}$ are just a padded version of some other problem in $\textbf{EXP}$?
I am familiar with the padding argument, which states that if $\textbf{P} = \...
2
votes
2
answers
82
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 ...
- 162
1
vote
0
answers
40
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
75
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 ...
- 162
1
vote
3
answers
41
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
16
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
44
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
77
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
45
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 ...
- 265
2
votes
1
answer
59
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
134
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
74
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
33
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 ...
- 225
0
votes
1
answer
17
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 ...
- 5
0
votes
0
answers
25
views
Finding the shortest 3-regular subgraph in a 6-regular graph
I am a research scholar currently working in computational complexity. As part of my research work, I need to understand the existence of various types of subgraphs in regular graphs. In particular, I ...
- 162
0
votes
2
answers
27
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
379
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 ...
- 37
0
votes
0
answers
54
views
Can the airline scheduling algorithm (network flow) be extended to handle seating capacities?
The airline scheduling problem determines the minimum number of airplanes required to service a set of passenger flights, where a plane can service routes A$\rightarrow$B and C$\rightarrow$D if there ...
0
votes
1
answer
42
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 ...
- 5,790
1
vote
1
answer
39
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 ...
- 219
0
votes
2
answers
144
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 ...
- 37
1
vote
0
answers
24
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
51
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
53
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,393
2
votes
2
answers
151
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 ...
- 289
1
vote
0
answers
76
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
183
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,469
2
votes
2
answers
283
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'...
- 512
1
vote
1
answer
120
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 ...
- 125
0
votes
1
answer
107
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,
...
- 237
1
vote
1
answer
57
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
29
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
56
views
Find a perfect matching with weights as close as possible to each other
Given a set of jobs $J$ and a set of machines $M$, where the link between machine $i\in M$ and job $j\in J$ has a positive weight $w_{ij}$. The problem is to select a perfect matching between the jobs ...
- 1,046
0
votes
2
answers
43
views
What happens in the event of a collision in a crypto hash function?
I was reading about hash functions in crypto and a website had mentioned that they were collision free, which obviously isn't possible if there are infinite input values that are mapped to outputs of ...
- 51
1
vote
0
answers
21
views
Algorithm Complexity Question
this is my first question on this site and I would like to preface this by saying I am not very savvy when it comes to Computer Science. So, I will try to ask this the best I can.
I was doing some ...
- 51
1
vote
1
answer
52
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
65
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
2
votes
1
answer
28
views
Finding all combinations of length k that has at least one of the pairs of T is in it
Let there be a list of $n$ elements $S$. Let $T$ be a set with $m$ elements ($m \leq nC2$), with each element in $T$ being a pair of distinct elements of $S$. For $k\geq2$, is there a polynomial-time ...
2
votes
1
answer
87
views
most cost-effective route w.r.t. gas in a labelled graph
Consider a car that can hold gas to travel a distance of $c \in N$ kilometers (its capacity) on a full tank that's initially empty. The car starts in node $s \in V$ of a graph. Each vertex $V_i$ of ...
- 2,469
1
vote
1
answer
60
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 ...
3
votes
1
answer
47
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 ...
- 229
0
votes
1
answer
23
views
Can we simply consider a pseudo random number generator to be a function $f: \Bbb{Z}_n \to \Bbb{Z}_n$ for ever-increasing $n$?
On modern architectures, random number generators get seeded by the current system time as a source of randomness, which is nice because it is kind of unpredictable when a process will switch to the ...
1
vote
1
answer
106
views
Minimum number of intervals to cover all possible colors
Given $n$ points in $\mathbb{R}$ each colored with one of following three colors
$$C=\{c_1, c_2, c_3\}.$$
In polynomial time, Choose the minimum number of intervals of length $1$ each containing some ...
- 250
1
vote
1
answer
270
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
1
vote
1
answer
53
views
Efficient comparison, using only sum, product, difference, and conditional jump if zero
I was wondering how small we could make the instruction set of a typical machine that supports a single datatype: arbitrary integers. If you need a heap, you declare an integer variable $h$ where you ...
-4
votes
1
answer
35
views
Polynomial-time Computable $f \circ g$. What does this implies for $f$ and $g$
Suppose that $f$ and $g$ are functions and $f \circ g$ is polynomial computable.
a) is it true that $f$ is also polynomial computable
b) is it true that $g$ is also polynomial computable
c) if we ...
2
votes
1
answer
208
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 ...
- 334