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
1 vote
1 answer
72 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 ...
Xfae's user avatar
  • 13
1 vote
0 answers
27 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 ...
Stevie's user avatar
  • 141
-1 votes
0 answers
125 views

Complexity of counting number of 3-literal set

Problem : Given a Set A of 3 sets each set inside Set A contains 2-literal subsets ,find how many unique 3-literal set we can make by selecting exactly one subset ...
Anuj's user avatar
  • 31
2 votes
2 answers
767 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 ...
S. M.'s user avatar
  • 1
3 votes
0 answers
35 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 ...
Bader Abu Radi's user avatar
1 vote
1 answer
43 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. ...
rus9384's user avatar
  • 1,600
0 votes
1 answer
53 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 ...
Yarin's user avatar
  • 275
0 votes
0 answers
27 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$ ...
rus9384's user avatar
  • 1,600
0 votes
0 answers
46 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? ...
Drat's user avatar
  • 1
3 votes
0 answers
81 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 ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
37 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 ...
CuriosityScream's user avatar
0 votes
1 answer
22 views

Enumerating proper intersections

Let $U \subset \mathbb{N}$ be a finite universe set; $B$ be a set of nonempty subsets of $U$ such that $B$ covers all elements in $U$, i.e. $\bigcup_{b \in B} b = U$, and if $b \in B$ then $b \...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
25 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} = \...
Zee's user avatar
  • 191
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 ...
Balchandar Reddy's user avatar
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 ...
LIR's user avatar
  • 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?
PatrickBateman's user avatar
0 votes
1 answer
242 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 ...
Balchandar Reddy's user avatar
1 vote
3 answers
49 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 ...
PatrickBateman's user avatar
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 ...
Lupital's user avatar
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 ...
Rishabh Kothary's user avatar
0 votes
1 answer
86 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 + ... + ...
automatically's user avatar
1 vote
1 answer
50 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 ...
Andrew Baker's user avatar
2 votes
1 answer
63 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 ...
Ank i zle's user avatar
  • 153
3 votes
0 answers
137 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$)....
Ank i zle's user avatar
  • 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 ...
Ank i zle's user avatar
  • 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 ...
Newberry's user avatar
1 vote
0 answers
34 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 ...
Philip Mayer's user avatar
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 ...
xxray's user avatar
  • 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 ...
Balchandar Reddy's user avatar
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, ...
Abhishek Manikandan's user avatar
-1 votes
2 answers
404 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 ...
Hjm's user avatar
  • 47
0 votes
1 answer
45 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 ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
43 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 ...
Colonizor48's user avatar
0 votes
2 answers
190 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 ...
Hjm's user avatar
  • 47
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$ ...
Daniel Donnelly's user avatar
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 ...
Robin Kurtz's user avatar
1 vote
1 answer
64 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 ...
rus9384's user avatar
  • 1,600
2 votes
2 answers
157 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 ...
Fred Jefferson's user avatar
1 vote
0 answers
93 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: ...
Nick Bishop's user avatar
6 votes
0 answers
184 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 ...
Albert Hendriks's user avatar
2 votes
2 answers
285 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'...
chausies's user avatar
  • 532
1 vote
1 answer
144 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 ...
Benicio Agüero's user avatar
0 votes
1 answer
117 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/...
Feyijinmi Adegoke's user avatar
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, ...
Avi Tal's user avatar
  • 237
1 vote
1 answer
66 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 ...
lucasbbs's user avatar
  • 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 ...
ORN's user avatar
  • 23
1 vote
1 answer
63 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 ...
zdm's user avatar
  • 1,046
0 votes
2 answers
49 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 ...
Joe's user avatar
  • 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 ...
Joe's user avatar
  • 51
1 vote
1 answer
62 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 ...
Niv's user avatar
  • 165

1
2 3 4 5
9