The polynomial-time tag has no wiki summary.
0
votes
0answers
76 views
Breaking secure pseudorandom generators by assuming BPP != P
Suppose we find some problem X that is in BPP but not in P. Also, suppose we have access to a random oracle R. Do X and R allow us to break any claimed secure pseudo-random number generator?
(Note ...
1
vote
0answers
69 views
Poly-time Algorithm for Non-Linear Optimization
As we know, linear programming is one of the most basic area of optimization theory, and computing an optimal solution can be excuted within poly-time. My question is about an extention of this ...
3
votes
2answers
165 views
Runtime of a TM enumerator
Is there a way to find out the time bound between 2 consecutive strings enumerated by a TM (the TM that decides this language is promised to run in linear time)?
For simplicity let's say the string ...
7
votes
1answer
138 views
Fitting minimum number of rectangles of width/height 1 into a 2D grid
Consider a problem in which you are given a 2D grid (e.g. a chessboard) where certain squares are occupied
and you need to put the minimum number of non-overlapping rectangles of any size w x h where ...
-3
votes
1answer
282 views
Help proving a 3CNF related prob. is in P
I need help proving that this problem is decidable in polynomial-time:
Input: a 3CNF formula with more than one clause.
Question: can the formula be divided into two satisfiable 3CNF formulas ?
...
10
votes
3answers
2k views
Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)
Answer: not known.
The questions asked are natural, open, and apparently difficult; the question now is a community wiki.
Overview
The question seeks to divide languages belonging to the ...
3
votes
2answers
229 views
Maximum fractional packing of spanning trees.
Given a graph $G$, let $\{T_1,\ldots,T_k\}$ be a set of spanning trees with associated nonnegative weights $\{w_1,\ldots,w_k\}$ such that for every edge $e$, $\sum_{e\in T_i}w_i \leq 1$. This is a ...
2
votes
1answer
244 views
Approximate bound/algorithm for “product of sums maximization” problem
I am looking for some approximate algorithm with upper/lower bound for the following problem:
Given a set of positive integers $\{a_1, a_2, \dots, a_n\}$, partition $\{1, 2, \dots, n\}$ into ...
5
votes
2answers
370 views
Choosing random permutations in “strict” polynomial time
This question compares "strict" polynomial time, as opposed to "expected" polynomial time.
Let $S = {1,2,…,n}$, and let $O$ be an ordering on elements of $S$. (The number of orderings is $n!$.)
A ...
21
votes
4answers
3k views
Why is 2SAT in P?
I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...
20
votes
2answers
498 views
What classes of mathematical programs can be solved exactly or approximately, in polynomial time?
I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The ...
17
votes
1answer
328 views
For which k is PLANAR NAE k-SAT in P?
The Not All Equal $k$-SAT problem (NAE $k$-SAT), given a set $C$ of clauses over a set $X$ of boolean variables such that each clause contains at most $k$ literals, asks whether there exists a truth ...
11
votes
1answer
383 views
NP-hardness of a special case of Number Partitioning
Consider the following problem,
Given a set of $n = k m$ positive
numbers $\{ a_1, \dots, a_n \}$ in
which $k \ge 3$ is a constant, we
want to partition the set into $m$
subsets of size $k$ so that ...
22
votes
2answers
732 views
Finding a prime greater than a given bound
Is a deterministic polynomial-time algorithm known for the following problem:
Input: a natural number $n$ (in binary encoding)
Output: a prime number $p > n$.
(According to a list of open ...
15
votes
2answers
737 views
How fast can we solve a totally unimodular integer linear program?
(This is a follow-up to this question and its answer.)
I have the following totally unimodular (TU) integer linear program (ILP). Here ...
8
votes
2answers
371 views
Which Integer Linear Programs are easy?
While trying to solve a problem, I ended up expressing part of it as the following integer linear program. Here $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ are all positive ...
