The tag has no usage guidance.

learn more… | top users | synonyms

7
votes
1answer
121 views

Two extremely naive questions about the Kronecker problem from Geometric Complexity Theory

I was reading the GCT IV paper (http://arxiv.org/pdf/cs/0703110v4.pdf) and while the representation theory is clear enough (by which I do not mean to say 'easy'!) the relation to complexity theory as ...
0
votes
2answers
154 views

Packing $n$ objects into $m$ bins whose size is variable

Assume we have $n$ fixed size objects with sizes $O_1$ to $O_n$. Also, assume we have $m$ bins with size $a \times B_1$ to $a \times B_m$ in which $a$ is a real number and $a\ge1$. We want to put ...
4
votes
0answers
40 views

Ground Reachability in String and Term Rewriting Systems

I have two questions concerning ground reachability in string and term rewriting systems. String Rewriting Systems: Let $\Sigma$ be a finite alphabet. I have a set of rules $R$ of the form $a_ib_i ...
3
votes
0answers
98 views

Voronoi diagram in presence of polygonal obstacle

Suppose there is a set of convex polygons ($\mathbb{P}$) on the plane. For each convex polygon $P_i$ there is one "facility" $f_i$ placed on the boundary of $P_i$. The distance between a point $p \in ...
5
votes
1answer
193 views

Canonical way of coloring graphs (individualization) for isomorphism purpose

Stefan Kratsch and Pascal Schweitzer in their paper Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs give a characterization of graphs on which Graph Isomorphism ...
1
vote
0answers
120 views

How does one sample uniformly at random from an uncountably infinite set?

I want to know if there are any examples of polynomial time algorithms which can sample uniformly at random from a given uncountably infinite set? (assuming it is possible) Does it help if the ...
10
votes
0answers
116 views

Hardness in P: methods to show optimality of $O(m^2n)$-like time?

In recent years, there has been exciting work in proving lower bounds for polynomial-time problems conditional on conjectures like SETH or "All-Pairs-Shortest-Paths (APSP) cannot be solved in ...
6
votes
5answers
239 views

Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)

What are some examples of problems with quasi-polynomial time ($QP$) algorithms that could conceivably be in $P$. In other words, they are in $QP$ for no obvious reason other than no one has found a ...
12
votes
4answers
711 views

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

László Babai recently proved that the Graph Isomorphism problem is in quasipolynomial time. See also talk at University of Illinois, Chicago, note from the talks by Jeremy Kun GLL post 1, GLL post ...
7
votes
1answer
208 views

Are there more polynomial time problems with complexity lower bounds?

I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below. Exponential Lower Bounds: Claim: If ...
1
vote
0answers
43 views

Multicuts (or multiway cuts) for 3 Terminals of Minimum Capacity

For each fixed $k \geq 3$, the following well-known problem is NP-complete. k-Multicut (aka "Multiway Cut", "k-Way Cut", "Multicut") Input: $(N,l)$ where $N=(V,E,T,c)$ is an undirected $k$-terminal ...
15
votes
2answers
466 views

Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

The $k$-cycle problem is as follows: Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges. Question: Does there exist a (proper) $k$-cycle in $G$? Background: For any ...
0
votes
0answers
41 views

How to find all alternating cycles wrt. a perfect matching?

Given an undirected graph $G$, Tarjan's bridge finding algorithm gives me the set of all bridges (edges that do not occur in any cycle) in $G$ in linear time. Now, I have a perfect matching $M$ in ...
1
vote
1answer
88 views

Polynomial-time reductions between undecidable languages

The Turing degree $\mathbf{0}'$ is defined as all languages Turing-equivalent to the halting problem. In fact any recursively enumerable language is polynomial-time reducible to the halting problem. ...
20
votes
1answer
742 views

Time complexity with irrational exponent?

Is there any natural problem in P for which the best known running time bound is of the form $O(n^\alpha)$, where $\alpha$ is an irrational constant?
10
votes
0answers
260 views

a geometric variant of k-medians. NP-hard or in P?

The following problem is a special case of k-medians. Is it NP-hard? Is it in P? Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$. Output: a ...
0
votes
1answer
67 views

polytime transformation from a graph to a set of binary strings

$d_H$ denotes the Hamming distance between two binary strings of the same size. The problem is stated as follows. Given any undirected graph $(V, A)$, does there always exist a one-to-one ...
2
votes
0answers
109 views

What is the most “unbalanced” vector between two given vectors of numbers?

Let $\mathbb{R}_+$ be the set of non-negative real numbers. Let $m$ be a positive integer and $\leq_m$ the product ordering on $\mathbb{R}_+^m$. That is, $\leq_m$ is the partial ordering on ...
6
votes
0answers
79 views

Complexity of solving vs verifying in P

Thinking of (seemingly) very different complexity of finding a solution to a NP problem and verifying it as the basis of practical cryptography, I am wondering if such separation is possible among ...
6
votes
1answer
2k views

Magic constant to solve NP-complete problem in polynomial time

Let's suppose that $P\ne NP$. Is that possible to solve all the instances of size $n$ of an NP-complete problem in polynomial time using some "universal magic constant" $C_n$ that has a polynomial ...
12
votes
3answers
3k views

Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?

Do you know of any problems (preferably at least somewhat well known), where, for a practical problem size, an exponential algorithm runs much faster than a best-known polynomial time counterpart. ...
9
votes
3answers
259 views

Is there a generalization of information theory to polynomially knowable information?

I apologize, this is a bit of a "soft" question. Information theory has no concept of computational complexity. For example, an instance of SAT, or an instance of SAT plus a bit indicating ...
14
votes
4answers
416 views

What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
0
votes
1answer
125 views

Any result connecting an NP-complete problem with slight super-polynomial time?

Helo everybody, is there any result or research that connects some $NP$-complete problem with only slightly super-polynomial (strongly sub-exponential) time? This would not necessarily ...
2
votes
1answer
183 views

Complexity of linear programming

It is known that Linear Programming (LP) is P-complete. I am interested in approximation algorithms for LP. There are numerous inapproximability results for NP optimization problems, e.g. it is ...
2
votes
5answers
487 views

Problems that are hard to prove in $\mathcal{P}$

What is the famous "hard" problems that were shown to be in $\mathcal{P}$ after? I want to know a list of problems that are difficult to prove in the class of "easy" problems? Maybe like matching, ...
2
votes
1answer
154 views

Proof-techniques for the hardness of optimization problems (esp. Polynomial time)

I've given an optimization problem for which I want to show that it is solvable in polynomial time. Now, I have two questions: Can this be done by formulating a mixed-integer linear program such ...
0
votes
1answer
92 views

What are some efficient algorithms for determining if a system of quadratic multivariate polynomials have a solution?

I know that in the general case it isn't efficient. However, I'm wondering if there are any good techniques in the quadratic case over the reals, specifically if there is a polynomial time solution.
2
votes
0answers
131 views

What are some efficient algorithms for finding the solutions to a quadratic multivariate polynomial?

Based on this question, there's an efficient algorithm to determine whether a quadratic multivariate polynomial has a root. What are some algorithms to enumerate these solutions? I'm interested in ...
2
votes
0answers
160 views

Most general form of SAT which is in P

2-SAT is in P. Additionally, a (CNF) SAT-problem is trivially poly-time solvable if no two expressions can be resolved (via Robinson resolution, ie for every pair of disjunctive clauses, they either ...
6
votes
4answers
510 views

What are some efficient algorithms for determining if a quadratic multivariate polynomial has a solution?

I know that in general, multivariate polynomial satisfiability is equivalent to 3-SAT; however, I'm wondering if there are any good techniques in the quadratic case, specifically if there is a ...
21
votes
1answer
430 views

Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

Precisely what the title says, I'm looking to find a polynomial time algorithm that given some set of matrices, will find if their span contains a permutation matrix. If any one knows if this ...
21
votes
1answer
341 views

Can $\{a^nb^n\}$ be recognized in poly-time probabilistic sublogarithmic-space?

Consider language $ \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} $. It is known that $ \mathtt{EQUALITY} $ cannot be recognized by any sublogarithmic-space alternating Turing machine (ATM) ...
5
votes
1answer
292 views

A reachability problem

Let $P$ be a length-preserving (i.e. $|P(x)|=|x|$) polynomial-time computable program. I. Given two strings $x$ and $y$, we want to decide if $y$ can be obtained by repeated applications of $P$ ...
1
vote
1answer
170 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
224 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
344 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
420 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 ? ...
11
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
346 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 ...
3
votes
1answer
361 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 ...
7
votes
3answers
657 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 ...
31
votes
4answers
10k 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? ...
26
votes
2answers
745 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 ...
18
votes
1answer
544 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
637 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 ...
23
votes
2answers
886 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 ...
18
votes
2answers
1k 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 ...
9
votes
2answers
583 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 ...