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
2
votes
1answer
56 views

How undecidable is it whether a given Turing machine runs in polynomial time?

The proof of Theorem 1 that PTime is not semi-decidable in this recent preprint effectively shows that it is $\mathsf{R}\cup\mathsf{coR}$-hard. The proof itself is similar to undecidability proofs at ...
3
votes
1answer
42 views

motivation and idea of defining non-deterministic Turing machine

This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms ...
4
votes
0answers
34 views

Conditional lower bounds on the running time of the single source shortest path problem

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
2
votes
1answer
37 views

Are chaotic systems computable in polynomial time

Suppose the parameters/inputs of the computation include the time at which the configuration of a particular deterministic chaotic system needs to be computed. Say, for instance, as input we have a ...
1
vote
0answers
47 views

Min-Ones-2-SAT getting to vertex cover

In the Min-Ones-2-SAT problem, we are given a 2-CNF formula φ and an integer k, and the objective is to decide whether there exists a satisfying assignment for φ with at most k variables set to true....
0
votes
0answers
33 views
1
vote
2answers
55 views

P/NP - Polynomial Reduction vs Certificate

I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate. How I understand polynomial reduction is that you can use it to ...
2
votes
0answers
33 views

Dynamic Program for this Weighted Possion-Binomial Problem?

Setup: Suppose we have $n$ independent Bernoulli random variables, say $\boldsymbol{X} = \{X_1, ..., X_n\}$ each with prior $\mathbb{P}(X_j = 1) = p_j$, and weights between $-1$ and $1$, say $W = \{...
5
votes
0answers
77 views

Is resampling random variables to maximize value NP-hard?

Setup Let $S = {X_1, ..., X_n}$ be a set of independent binary random variable, i.e. $X_i \in \{0, 1\}$, each with prior $P(X_i = 1) = p_i$. The $X_i$ are not iid, so $p_i, p_j$ need not be equal if $...
1
vote
1answer
23 views

Use Fact to decompose a given number

Let Fact be the following decision problem. Given two natural numbers $k \le n$ the machine accepts if and only if $n$ has a non-trivial divisor that is less than or equal to $k$. Prove that if Fact $\...
0
votes
1answer
37 views

Difference Between PTAS and FPTAS [duplicate]

According to this link: Polynomial Time Approximation Scheme (PTAS) is a type of approximate algorithms that provide user to control over accuracy which is a desirable feature. These algorithms ...
1
vote
0answers
21 views

Useful conditions for proving super polynomial lower bound for some kind of recurrences

Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$ Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...
1
vote
1answer
56 views

Simple Hamiltonian cycle reduction

HAMPATH Input: An undirected graph $G$ and 2 nodes $s, t$ Question: Does G contain a Hamiltonian path from $s$ to $t$? HAMCYCLE Input: A undirected graph $G$ and a nodes $s$ ...
0
votes
2answers
54 views

How many combinations will be generated if below conditions are put?

I need a generalized formula for a set having size(s) having below restrictions, for ex. X = 2,7,11,17,26 I want only the first combination 2+7 & ignore all of the combinations that start from 2+...
2
votes
1answer
36 views

Number of equivalence classes in $P$

I am currently taking a course which involves computational complexity. I was told that polynomial equivalence (polynomial time reduction) divides P into exactly 3 equivalent classes, namely $\phi$ , $...
0
votes
1answer
78 views

is $x^{100000000000}$ a “polynomial time”?

per this post $t = x^2$ means the problem is solvable in "Polynomial" time. per this post in the form $$a_{n}x^{n}+a_{n-1}x^{n-1}+\dotsb +a_{2}x^{2}+a_{1}x+a_{0} { > \boldsymbol{=0}}$$ ...
1
vote
2answers
131 views

Reduce 4-SAT to 5-SAT

given is a reduction from 4-SAT to 5-SAT. How is it possible to describe such a function? I found some informations about reduction 3-SAT to 4-SAT here, but it can't help me so much.
0
votes
0answers
28 views

Is retrospective inference NP-hard?

Here is a minimal working example of the question: Consider a network with nodes arranged in a pyramid: $1$ node in the first row, $1+d$ nodes in the second, $1+2d$ nodes in the third, and so on, ...
2
votes
0answers
41 views

Is a “stacked”, “local” version of 3-SAT NP-hard?

In this previous question, I learned that if each variable in a string $C \in 3\text{-SAT}$ appears only "locally", then finding a satisfying assignment is no longer NP-hard. My question below builds ...
7
votes
1answer
404 views

Is a “local” version of 3-SAT NP-hard?

Below is my simplification of part of a larger research project on spatial Bayesian networks: Say a variable is "$k$-local" in a string $C \in 3\text{-CNF}$ if there are fewer than $k$ clauses ...
1
vote
0answers
36 views

Smallest string containing sets of letters

I am looking for a solution to this problem: Given multiple sets of letters (Set0={a,b,c,d}, Set1={d,e,f,g}, Set2={a,b,e,g}, ...), what is the minimal length of the string containing all the sets. The ...
3
votes
1answer
212 views

Minimum diameter spanning tree problem

Minimum diameter spanning tree (MDST) problem is defined as following: given the connected weighted graph $G(V, E)$, weight function $w: E \rightarrow R, w(e) > 0\ \forall e \in E$, find the ...
1
vote
1answer
94 views

Polynomial Time reducible explanation

Have a set of examples given to me, but I'm pretty sure they're all wrong. Can someone verify that my understanding of them is correct? If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X ...
0
votes
1answer
52 views

Complexity of an encoded turing machine

This is an example of an assignment question, there are 3 of them so I created my own in order to better understand it. First, we have the variable m which is a ...
1
vote
0answers
133 views

CRC computation speed vs polynomials features

I tried to find information about how features of a CRC polynomials influence computation speed of implementations. It is obvious that (depending from the CPU architecture the algorithm runs on) ...
4
votes
0answers
131 views

Subset Sum Search Problem for Input with At Most One Solution [closed]

Edit: This question has been reasked on TCS. We first consider the search version of the subset sum problem: Given a set $S$ of $n$ naturals, find a subset of $S$ that sums to exactly $W$. My ...
1
vote
1answer
110 views

Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology?

Is the following true or false? Why? Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq_{p} X$.
2
votes
2answers
50 views

Calculating the number of assignments satisfying a general propositional formula

I know, for a disjunctive clause of the form $x_1 \vee ... \vee x_i$, the number of assignments satisfying it is simply $2^i - 1$, but what about for a general formula? Is the number of satisfying ...
0
votes
0answers
36 views

Is the succinct version of P-complete problems out of P?

Consider the succinct versions of the P-complete problems as a Boolean circuit which represents its input in exponential more succinct ways. Could these succinct versions are in P or out of P?
2
votes
1answer
114 views

Polynomial Time Algorithm for Steiner Tree Problem

I know about Steiner Tree Problem. It is stated as Input to Steiner Tree Problem is a weighted graph G and a subset T of the nodes (called terminal nodes) and goal is to find a minimum weight tree ...
1
vote
1answer
31 views

Determine whether a system of $n$ linear equations has solutions in $\{0, 1\}^n$ in polynomial time

I'm trying to determine whether it is possible to decide if a system of $n$ linear equations with integer coefficients and $n$ variables has a solution in $\{0, 1\}^n$ in polynomial time. ...
2
votes
1answer
43 views

Are you allowed to change the specifications of a problem when doing reductions?

I'm doing a polynomial time reduction from problem A (known graph problem) to problem B (funky and specific longest path problem). There is a lot of demands on how problem B is supposed to be solved. ...
0
votes
1answer
56 views

Sat instance size and definition of TIME(f(n))

Sat usually is defined as the language of a 'reasonable' encoding of satisfable Cnf formulas over n variables. Question: a Cnf formula over n variable with m clauses has a size (as a function of n) ...
1
vote
1answer
90 views

Find Hamiltonian cycle in polynomial time

I want to know for what types of graph it is possible to find Hamiltonian cycle in polynomial time. It would be helpful also to show why on some types of graph finding Hamiltonian cycle would be only ...
2
votes
0answers
55 views

Modular reduction in a finite field

Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ ...
1
vote
1answer
200 views

Relation beetween log-space reduction and polynomial time reduction

I read somewhere that given two languages A and B, if A <=(log) B, then A <=(P) B (with <=(log) the log-space reduction and <=(P) the polynomial time reduction), but I'm not sure about the ...
1
vote
0answers
48 views

Finding simple min-weight path between two vertices in graph with negative edge weights

Given a weighted graph (negative weights are allowed) and two vertices $u$ and $v$, can we find the simple min-weight path between $u$ and $v$? There can be a negative cycle on the path from $u$ to $v$...
2
votes
0answers
43 views

Theoretical performance measures other than worst case

Suppose that $P \neq NP$, and $P = BPP$. Assume one is given a decision language $L \in NPC$, and she has only polynomial time turing machines. Additionally, she can't use randomness (not sure that's ...
0
votes
1answer
51 views

Understanding integer factorization is NP [duplicate]

I can see that Integer factorization problem is in NP. I am looking for a simple intuition behind this. For example if we take the problem of sorting the complexity is $n\log n$ for merge/quick sort ...
1
vote
0answers
22 views

Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
2
votes
1answer
28 views

Is there a “well known” example of a constraint satisfaction problem on a 3-element set which is polynomial-time solvable?

I'm basically looking for an example (in maybe graph theory) of a constraint satisfaction problem which has a 3-element set as a domain and the problem is known to be polynomial-time solvable.
0
votes
1answer
75 views

Existence of polynomial time reduction from P to R?

Why the next idea doesn't work: If L_2 in R and L_1 in P and the languages are not trivial, then there is a polynomial-time reduction from L_1 to L_2 I know ...
4
votes
1answer
43 views

Probability of randomly designated subsets cover the universe

Let $U=\{1,2,\ldots,n\}$ and $S \subseteq \mathscr{P}(U)$. Let $T$ be a subset of $S$, randomly constructed selecting independently each element of $S$ with probability $p$. Is there a polynomial ...
1
vote
1answer
72 views

Polynomial Complexity (Relative to the Size of the Input)

I came across the following statement: "Since b is smaller than n, the complexity $O((n + mb)^3)$ is polynomial." I suppose it has something to do with the notion of polynomiality in terms of the ...
2
votes
1answer
276 views

Proving special case of SAT is in P

Let SAT-100 be the following problem: Input: Any boolean logic formula Output: True if there exists a combination of exactly 100 input variables that satisfy the formula. This is the description of ...
12
votes
2answers
239 views

Problems that feel exponential but are P

I'm trying to build a list of algorithms/problems that are "exceptionally useful", as in, solving problems that 'seem' very exponential in nature, but have some particularly clever algorithm that ...
5
votes
2answers
59 views

Given $k$ points in $n$-dimensions, such that $n\geq3$, is there a polytime algorithm for finding a curve that splits them into 2 sets of points?

So in this math exchange question I asked, it was proven that for $n>2$ dimensions, you can always find a curve that separates $k$ points in $n$-dimensional space into $2$ arbitrary sets that you ...
0
votes
1answer
120 views

Is the spigot algorithm for $\pi$ useful for computing all the digits of $\pi$?

I'm asking the question here because it's not a purely mathematical question and the answer also depends on how computers work. I think that according to the Wikipedia article Bailey–Borwein–Plouffe ...
1
vote
1answer
30 views

polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$

If we have two languages $L_{1} \subseteq \Sigma^{\ast}_{1}$ and $L_{2} \subseteq \Sigma^{\ast}_{2}$ I proved that when $L_{2} \in \textbf{P}$ and $L_{1} \leq_{p} L_{2}$ then $L_{1} \in \textbf{P}$ ...
2
votes
1answer
94 views

Complexity of polynomial interpolation

Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of ...