Questions tagged [polynomial-time]

Question 1

I happen to be working on a problem whose decision version is trivial (decidable in uniform $\mathsf{AC^0}$) but whose search version is only known to be solvable within $\mathsf{FP}$. I have been ...

Question 2

Consider a poly-time algorithm that attempts to solve the GI problem on general graphs. However, the algorithm can only guarantee that it correctly decides the problem for a specific range of values ...

Question 3

In this answer about the question $BPP \stackrel{?}{=} P$ it is written: To me, the intuitive reason for believing that $BPP = P$ is that if you describe to me a randomized algorithm, then in ...

Question 4

Let $q : \mathbb{N} \to \Sigma^*$ be in $\mathrm{poly}$ (that is, $|q(n)|$ is polynomially bounded; the definition is essentially the good ol' "advice" from $\mathrm{P/poly}$). Also, let $M \...

Question 5

Let $A_n \subseteq \mathbb{N}, n \in \mathbb{N}$ be cofinite, but not necessarily computable as a function of $n$. Does there always exist a function $f$ such that $f$ has a polynomial-time Turing ...

Question 6

Consider a sequence of polynomials $\{p_n(\cdot)\}_{n=1}^\infty$ where $p_n$ is of degree doubly exponential in $n$, i.e. $deg(p_n) = 2^{2^n}$. Suppose there is an algorithm that on input $1^n$ ...

Question 7

Recently, I wrote a paper (not published yet) about an algorithm that calculates the chromatic number of any graph in polynomial time. I have mathematical proof to support it, but it needs ...

Question 8

I'm interested in applications of optimal programs that convert one formal language into another (in particular Python to C++) so this seems highly related. I am thinking along the lines of "...

Question 9

The 3SUM problem is defined as follows: Given three sets of integers $A,B,C \subseteq \{-W,\ldots,W\}$ for $W = n^3$, each containing $n$ integers, determine whether there exsists some $a \in A, b \in ...

Question 10

I'm having difficulty solving the following problem: We're given $n$ sets $X_1,\ldots, X_n$. Each set $X_i=\{(a_i,b_i)\}$ contains poly(n) many ordered pairs of non-negatives with $0\le a_i+b_i\le 1$. ...

Question 11

We know that FO[LFP] captures PTIME on the class of ordered structures. However, I have difficulties interpreting this result. From what I understand, it means that, given a constant, finite alphabet $...

Question 12

Many combinatorial optimization problems can be described as follows. We are given a set system $(E,I)$, where $I \subseteq 2^E$ and a weight function $w: E \rightarrow \mathbb{N}$. The goal is to ...

Question 13

Let $v_1,\dots,v_n$ be a basis of a vector subspace of $\Bbbk^N$, say for $\Bbbk$ a finite field. I would like an algorithm to find a linear combination of the $v_i$'s with small support, i.e. with ...

Question 14

$K^{poly}$, as well as other related problems such as $MCSP$, is believed to be hard on average [1, 2] when the input is sampled from a uniform distribution (since otherwise one way functions, pseudo-...

Question 15

For a universal Turing machine $U$, the time bounded Kolmogorov complexity of a string $x$ is silmilar to the usual Kolmogorov complexity but limited to programs $p$ running in time at most $t(|x|)$: $...

Stack Exchange Network

Questions tagged [polynomial-time]

Complexity gaps within P in search vs decision

Status of the Graph-Isomorphism problem when $n\le k$ for some $k$

Can we turn Miller-Rabin primality testing into a deterministic algorithm?

Polynomial-time approximation of poly advice

Polynomial time function with values from cofinite sets

Efficiently computing approximations to high dimensional polynomials?

Seeking Help to Verify Algorithm for Chromatic Number in Polynomial Time

On what functions on strings of length $n$ are we able to compute the Kolmogorov complexity and also exhibit an optimal program?

3SUM Reduction to Distinct Pairwise Sum [closed]

Minimizing a submodular function containing summation and production under partition matroid constraint

Are classes of graphs represented by adjacency matrix ordered structures?

distinguishments between query complexity of membership oracles and standard time complexity

Find linear combination with small support

Resource bounded Kolmogorov complexity hardness on average over a non uniform distribution of inputs

Fast algorithms for time bounded Kolmogorov complexity

Hot Network Questions