# Questions tagged [computational-complexity]

For questions about the theoretical runtime needed for solving computational problems, often measured in the size of the input. This includes questions about whether polynomial time algorithms exist, NP-hardness, among others.

69 questions
Filter by
Sorted by
Tagged with
1 vote
72 views

### interior point computational complexity for SDP

I am trying to get the complexity of the SDP problem for my specific problem, but I’m facing some problems. I found in the literature that the complexity of the SDP problem for an interior point per ...
• 11
121 views

### Is OCN=DOCN decidable?

One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that cannot decrease below zero and cannot be explicitly tested for zero. An OCN $A$ over alphabet $\sum$ accepts a ...
• 21
675 views

### How many variables and constraints can modern mixed integer programming solvers handle?

I originally asked a question here and they suggested that I crosspost it to the OR stack exchange, so that is what I am doing (hopefully correctly?). Here is the question I asked there: "I know ...
1 vote
78 views

### Polynomial time separation and optimization for an LP with exponential columns and rows?

We know the fundamental theorem on the equivalence of separation and optimization: an optimization problem can be solved in a polynomial time if and only if there is a polynomial time separation ...
• 11
1 vote
109 views

• 524
110 views

### How many clues make Sudoku polynomial

Consider a $n^2 \times n^2$ grid sudoku. Define a clue to be composed of a coordinate $x$ and $y$ of the grid and a value $z$. The goal is given $n$ and a set of clues, to find one solution to the ...
126 views

### Complexity of the ellipsoid method in general convex problems

The ellipsoid method is often mentioned in relation to the complexity of solving linear programs. Is the method however polynomial in the general non-linear convex cases? Preferably I would like a ...
• 622
291 views

### Reformulate CPLEX optimization model of Warehouse Product Allocation

I am trying to optimize the allocation of of products inside a fictive warehouse, having a predefined number of aisles (3 in the example code below) where products ...
114 views

### Traveling Salesman Reference

Can anyone recommend a reference which shows the amount of time required for the Traveling Salesman Problem (TSP) to be solved using brute force as the number of cities increase? I have informally ...
• 1,821
531 views

### Optimization Solution Framework

I am working through Pascal Van Hentenryck's excellent discrete optimization course on Coursera. While the course certainly touches on it in some ways, I am looking for more of a framework in terms of ...
• 117