# Constraints

## 15 August 2010

### A simple reduction

Filed under: Commentary — András Salamon @ 3:01
Tags: ,

Recent online discussion about computational complexity included the notion that the structure of solutions of SAT might be useful in proving separation results. I want to point out a further obstacle to this idea. (more…)

## 13 August 2010

### P not equal to NP (P ≠ NP) consequences

Filed under: Commentary,Question — András Salamon @ 20:43
Tags:

During the discussion about Vinay Deolalikar’s manuscript, many people commented about the consequences that would follow if we knew that P ≠ NP. I’d like to discuss these consequences in a little more detail.
(more…)

## 9 August 2010

### Deolalikar’s manuscript

Filed under: Commentary — András Salamon @ 17:39
Tags: ,

Given the sudden influx of visitors, it seemed apposite to talk about Vinay Deolalikar’s manuscript titled $P \ne NP$ (or in words, “P is not equal to NP”). (more…)

## 15 April 2010

### k-ISOLATED SAT

Filed under: Commentary,Question — András Salamon @ 13:29
Tags:

How fast can one decide if a SAT instance has an isolated solution? (more…)

## 10 February 2010

### Is P=NP a reasonable hypothesis?

Filed under: Commentary,Question — András Salamon @ 13:00
Tags:

Does it even make sense to ask “what if P = NP?”, or is this nonsense? (more…)

Blog at WordPress.com.