# 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.

49 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
288 views

### P vs NP and the Time Hierarchy

Assuming $P\neq NP$, is it possible that there exists a $k$ such that $P\subseteq\textsf{NTIME}(t^k)$? There reason I ask this is that I assume the following: P=NP \implies \forall k\ \exists j.\ \...
123 views

140 views

### Time complexity of languages recognized by linear bounded automata with restricted number of writes

Suppose that $L$ is a language recognized by a linear-bounded automaton with the constraint that it can only change each of its input cells at most $t$ times each, where $t$ is some constant integer. ...
44 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 ...
118 views

### How to find a minimum spanning forest with a constrained number of nodes in each spanning tree?

Consider a weighted undirected acyclic graph consists of m source (root) vertices and n target vertices. The m-spanning tree problem of the graph is defined as that: (1) each of the m spanning trees ...
71 views

### How to find m directed paths connecting the maximal number of vertices in an unweighted directed acyclic graph?

Consider an un-weighted directed acyclic graph (DAG) consists of m source (root) vertices and n target vertices. When there is only one source vertex (m=1), the problem to find a directed path ...
31 views

### Are there problems that are known to be in ZPP but not in p

Are there any problems that are known to be in ZPP but not in p?
57 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)$ ...
44 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 ...
89 views

### polynomial time reducibility, if $A \in \mathbf P$ and $B \in \mathbf N$ $\mathbf P \setminus \{\emptyset,\Sigma^*\}$ and vice versa

$f: \Sigma^* \to \Sigma^*$ is a polynomial time computable function if some poly-time Turing Machine M, on every input w, halts with just $f(w)$ on its tape. Language $A$ is polynomial time reducible ...
243 views

### Building a poly-time verifier given a poly-time decider

Can I build a polynomial time verifier for problem, given a non-deterministic polynomial time decider for that problem? I assume I should modify the decider such that it will verify the certificate. ...
52 views

### Longest cycle, existance of approximate algorithm implies existence of better one

This is an exercise from an old exam that I don't know how to solve. For any undirected graph $G$, let $c(G)$ be the length of the longest (simple) cycle in $G$. Show that if there exists a ...
47 views

### Cobham's characterization of FP

Does anyone know of an accessible introduction to Cobham's model independent characterization of FP and it's equivalence to the standard definition using Turing machines? The best source I could find ...
62 views

### Can we decide if a number is a power of any given $K$ in polynomial-time?

It is simple to decide powers of 2 in $O(n)$ time because it's just "0-bit Unary" after bit-1. (eg. $1000$ is a power of 2 in binary). I haven't found many other trivial powers of $K$ that ...
25 views

### Seeking guidance on what to read for Feasibility Binary IP with ''almost total unimodular'' (-1, 0, 1)-Coefficient Matrix and No Obj Function

I am working on an algorithm in graph theory which I wish to prove it's polynomiality/NP-hardness. I am investigating a binary variable (0, 1) integer program which has the coefficient matrix ...
46 views

142 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....
22 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 ...
37 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 ...
218 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) ...
55 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$...
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 ...
98 views

### What are widely-used, practical applications to come from the study #P problems?

When, beyond theoretical exercises, do we care how many solutions we can find for something? I had an analogous question for TMs before - why is it useful to study machines that can only deliver ...
35 views

### Pedagogic reference on cut generating functions

Can you recommend an introduction to the topic of cut generating functions? I am looking for introductory or review-like material. I did find the following survey paper, but it seems to be addressed ...
33 views

### Mixing time of three particle systems

Is there anything known about mixing time of Markov chains for three particle systems? It is proved here http://www.ams.org/journals/tran/2005-357-08/S0002-9947-05-03610-X/S0002-9947-05-03610-X.pdf ...
34 views

### Is this problem in P: Finding a common key for a collection of systems of equations?

Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all ...
29 views

### Reconstructing an Array via Time-Intensive Subset Queries

I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem. I am given access to an ...
14 views

### Global-input-local-output p-time algorithms

Are there polynomial-time algorithms whose input is global but output is local in nature? What I have in mind is a problem instead of an algorithm. Itās the satisfiability (SAT) problem. Each clause ...
28 views

### Looking for fast LP solver algorithm for my Special case

I am interested to know what is the fastest algorithm (complexity wise) known to us to solve the following linear program. Due to its simplicity, I hope for a very fast algorithm. Your help is greatly ...
26 views

### What's the class of problems solvable in polynomial time with an exponential number of processors?

What's the class of problems solvable in polynomial time with an exponential number of processors? I am asking this because I'm curious about the class of problems that could feasable be solved on a ...
11 views

### Logic of the squared running time in “A Variant of Nondeterministic Acceptance”

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman, Motwani where I came across the following claim: A Variant of ...
17 views

### Applying Polynomial Time Approximation Scheme (PTAS) on an Algorithm

I am trying to apply PTAS on an algorithm. I think that we apply PTAS on the running time equation of the algorithm. We use the term (1-Ļµ) and (1+ Ļµ) in the running time of the algorithm but I donāt ...
12 views

### Search reduction to decision

I'm a little stumped on this question (and I don't know the name of it, which is why I've excluded it from the title). I need to describe an algorithm that finds a solution to an NP-Hard problem given ...
35 views

### Why is “encoding” important in time complexity?

I read many writing about the time complexity of 0-1 knapsack problem. (https://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial#answer-4538668) In conclusion, the ...
31 views

### Solving NP problems : analogy between the SAT problem and the shortest path problem

in this 2minute-long video https://www.youtube.com/watch?v=TJ49N6WvT8M (pulled from a free udacity course on algorithms/theoretical computer sciences), whose purpose is to show how a SAT problem can ...
34 views

### If two languages are reducible to the same third language, are they necessarily reducible to one another?

Speaking of polynomial time reductions.
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, ...
43 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?
33 views