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
0 votes
1 answer
16 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/...
user avatar
3 votes
2 answers
762 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, ...
user avatar
  • 183
0 votes
0 answers
12 views

A simple clarification on polynomiality of sequential construction of Turing Machines through plus construction

Suppose our original $NDTM$ $M_0$ has $N<2^t$ number of acceptance paths. We construct $r$ different $NDTM$s $M_1,\dots,M_r$ with each with $m_1,m_2,\dots,m_r$ acceptance paths respectively where $...
user avatar
1 vote
1 answer
27 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 ...
user avatar
  • 113
1 vote
0 answers
28 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 ...
user avatar
  • 23
1 vote
1 answer
41 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 ...
user avatar
  • 1,016
0 votes
2 answers
37 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 ...
user avatar
  • 51
1 vote
0 answers
20 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 ...
user avatar
  • 51
1 vote
1 answer
31 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 ...
user avatar
  • 135
0 votes
0 answers
35 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, ...
user avatar
0 votes
0 answers
21 views

Does deciding the following language take polynomial time or constant time?

I've written an algorithm that decides the following language: $$ \{ \langle G, H \rangle \mid G, H \text{ are undirected graphs, } \lvert V_H \rvert \leq 10 \text{ and } G \text { is isomorphic to a ...
user avatar
2 votes
1 answer
23 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 ...
user avatar
0 votes
0 answers
28 views

Master theorem not applicable because "polynomially" slower

From what I understand the Master Theorem can't be applied when a function is slower or faster but not "polynomially greater or slower" what does polynomially faster or slower mean ?
user avatar
2 votes
1 answer
77 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 ...
user avatar
1 vote
1 answer
21 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 ...
user avatar
3 votes
1 answer
33 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 ...
user avatar
0 votes
1 answer
19 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 ...
user avatar
0 votes
0 answers
34 views

Polynomial reduction to SAT with a condition

Let L be in NP. Is there always a reduction from L to SAT where atleast m-1 clauses (m being the number of clauses in the CNF formula) can be satisfied? When w is in L it is trivial because the ...
user avatar
1 vote
1 answer
33 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 ...
user avatar
1 vote
1 answer
56 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 ...
user avatar
  • 13
1 vote
1 answer
52 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 ...
user avatar
-4 votes
1 answer
31 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 ...
user avatar
2 votes
1 answer
47 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 ...
user avatar
  • 314
30 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 ...
user avatar
  • 442
11 votes
4 answers
3k views

Is there an algorithm whose time complexity is between polynomial time and exponential time?

We often hear about some algorithms' running time that is polynomial, and some algorithms' running time that is exponential. But is there an algorithm whose time complexity is between polynomial time ...
user avatar
  • 141
0 votes
3 answers
165 views

Examples of time complexity $O(n^k)$

I am looking for some algorithms(examples) whose time complexity is given by $O(n^k)$. It could be any problems that you have come across. Please reply. Thanks!
user avatar
1 vote
0 answers
22 views

Computational Hardness of the $k$-Partition Problem with identical numbers/objects?

The $k$-Partition Problem is NP hard. I want to know if some slight modification of this problem makes it polynomially solvable. Now consider the set $S=\{a_1,\ldots,a_n\}$ of IDENTICAL numbers/...
user avatar
-2 votes
1 answer
34 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 ...
user avatar
  • 1
3 votes
1 answer
76 views

Subset sum with only two item types

Suppose we have $r$ copies of the integer $a$ and $t$ copies of the integer $b$, and a capacity $C$. We would like to find the maximum sum of the given integers, that is at most $C$. This is a special ...
user avatar
1 vote
1 answer
76 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 ...
user avatar
  • 149
0 votes
1 answer
56 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 ...
user avatar
0 votes
1 answer
40 views

Reduction of np to npc

Given that $A$ is $NPC$ problem. And I need to check "if $D$ belongs to $NP$ and $D\leq_p^\mathsf{}A$ then $D$ is $NPC$" is true or not? My approach: Since $D\leq_p^\mathsf{}A$, therefore $...
user avatar
  • 1
1 vote
1 answer
33 views

Is the clique problem polynomial-time solvable still in unit disk graphs allowing different sized disks?

Clark et al. proved that the clique problem is polynomial-time solvable in unit disk graphs. Does anyone know if this result holds still if the disks are allowed to be different sizes? Or do such &...
user avatar
3 votes
1 answer
38 views

Using the chromatic number to compute an optimal coloring

Suppose we are given a graph $G$ of order $n$ and a black box that can efficiently (polynomial time) compute the chromatic number $\chi(G)$. I am curious to hear how would one go about in order to ...
user avatar
  • 2,420
4 votes
1 answer
660 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 ...
user avatar
  • 1
0 votes
1 answer
198 views

If $A\leq_m^\mathsf{}B$ and $B$ is a regular language, does that imply that $A$ is a regular language?

Corollary:1 We know that if $A\leq_m^\mathsf{}B$ and $B$ is decidable then $A$ is also decidable. This is because if there exists a specific algorithm for solving $B$ and we can also reduce $A$ to $B$ ...
user avatar
  • 1
0 votes
1 answer
77 views

Reduction from recursive language to recursive enumerable

If any language $L_1$ reduces $L_2$ in polynomial time $L_1\leq_p^\mathsf{}L_2.$ If $L_1$ is recursive then $L_2$ is recursive and recursively enumerable, is it true? Because $L_2$ is at least as ...
user avatar
  • 1
2 votes
1 answer
36 views

Do graphs with a bounded number of incident edges have a polynomial-time subgraph-isomorphism algorithm?

It is well known that the subgraph isomorphism problem is NP-complete. And so a polynomial-time algorithm for solving it would mean P = NP. Thus I'm interested in whether a bounded version of the ...
user avatar
0 votes
1 answer
57 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 \...
user avatar
  • 103
2 votes
3 answers
681 views

Are there problems in NP that do not reduce in polynomial time to any problem in NP?

As the title says: are there problems in $\mathbf{NP}$ that do not reduce in polynomial time to any problem in $\mathbf{NP}$?
user avatar
  • 31
3 votes
2 answers
195 views

Subset Sum With Interval Target

Define the subset sum with interval target problem (SSITP) as follows: SSITP Input: A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$ such that $\sum_{a_i \in S} a_i = T$. SSITP Output: ...
user avatar
1 vote
0 answers
67 views

Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?

From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $S$ of $n$ integers, and an integer $m$, the goal is to ...
user avatar
0 votes
0 answers
47 views

Pseudo-polynomial Algorithms

Reading wikipedia I found that they give this example Consider the problem of testing whether a number n is prime, by naively checking whether no number in $\{2,3,\dotsc ,\sqrt {n}\}$ divides $n$ ...
user avatar
  • 263
0 votes
1 answer
61 views

Differences between Polynomial and fully polynomial time approximation scheme

I have a confusion on understanding the relation between: The input n ,The relative error and The running time of the program In both PTAS and FPTAS. In "The running time of PTAS must be ...
user avatar
  • 13
0 votes
1 answer
40 views

Polynomial and fully polynomial time approximation scheme

How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program? Is there any other way to decide?
user avatar
  • 13
2 votes
1 answer
79 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 ...
user avatar
  • 207
1 vote
2 answers
126 views

Need the type of time complexity and its formula

If the complexity of my problem is $O(f_n(n))$ begins at $n =4$ and increases in this sequence: At $n = 4$ the number of operations = $(n - 2)$, $n = 5$ the number of operations = $((n - 2) (n-2)(n-...
user avatar
  • 13
-4 votes
3 answers
95 views

What is wrong with this argument that if A is NP Complete, but B is in P, then A\B is NP Complete and B\A is NP Complete as well?

The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more: Suppose ...
user avatar
2 votes
2 answers
128 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 ...
user avatar
  • 261
1 vote
2 answers
101 views

"Polynomial Counter" Turing Machine

I need some help with this question: Definition: A Turing-machine that is a counter for the language $L$ is called 'polynomial counter' if there exists a polynomial $p$ s.t. every word $w\in L$ ...
user avatar
  • 13

1
2 3 4 5
8