Archive for the ‘complexity’ Category

Over the last year or so I became interested in a family of problems related to linear programming. In ordinary linear programming, we are given some collection of linear constraints, say {ai x ≥ bi} for i=1, …, n, and the x represents a d-dimensional variable. A central result in optimization says that there is […]

Let’s say I hand you a bunch of polynomial equations/inequalities and some variables, e.g., {x > 0, y < x, x2-y3+z=0, z4+4z>16} in variables x, y, z. Either there exists a triple of values for which all the equations and inequalities are satisfied, or there doesn’t. How can you tell? Is there an efficient procedure […]

In the spirit of Tetris, Sudoku, Minesweeper, and other games, we recently determined at the C&O open problem session that the game Polarium Advance is NP-complete. There is a pretty straightforaward reduction from “Hamiltonian path in induced subgraph of a grid graph” to Polarium Advance. That problem can be reduced from “Hamiltonian path in bipartite […]