Forgot your password?
typodupeerror

Comment: Potential pitfalls in the Finite Model Theory bits (Score 5, Interesting) 457

by gatesyy (#33187114) Attached to: Claimed Proof That P != NP

Being a researcher in Finite Model Theory (FMT) this paper is very interesting because it uses ideas from that area, i.e. the LFP(FO) bits. Reading through the proof synopsis and scanning the FMT sections there are several potential pitfalls:

  1. 1. The logic LFP(FO) only captures P on ordered structures; that is structures that have a built in total ordering relation.
  2. 2. Any sentence that describes a problem in LFP(FO) must be order-invariant ; that is it must work for any possible ordering of the vertices in the underlying graph/structure.

It is already known that LFP(FO) on unordered structures is a proper subset of LFP(FO) on order structures, so if the ordering and order-invariant requirements for LFP(FO) = P are not dealt with in the proof, then all the author has done is proof that LFP(FO) on unordered structures is a proper subset of NP. Which is already known.

Another potential problem is in the arguing that all first-order properties are local (Hanf's Theorem) in the presence of ordering, as every vertex is effectively connected to every other vertex (Immerman's proof of LFP(FO) = P requires total ordering of the underlying graph/structure), and hence every vertex is in the radius = 1 neighbourhood of every other vertex.

The crucial step in the proof, appears to be the argument that no LFP(FO) formula can extend a partial solution to k-SAT to a full solution to k-SAT. This is where I'd check the logical steps of the proof, and also make sure that the ordered nature of LFP(FO) structures is correctly considered.

I look forward to seeing this published in a peer-reviewed mathematics journal: I'd recommend to the author the "Journal of the ACM" for this (as it's one of the best journals in the field).

Wii

Should the Gov't Pay For Injured Man's Wii? 222

Posted by kdawson
from the if-the-wii-fits dept.
An anonymous reader writes "Politicians in the Australian state of Victoria are currently locked in a debate about whether an injured man should be able to claim the cost of a Nintendo Wii for rehabilitation purposes under worker's compensation. The man's doctor apparently recommended he use the Wii Fit exercise device, but both insurance companies and the government itself have blocked the payment and have now ridiculed the idea as paying for video games. But with the Wii Fit increasingly being used for rehabilitation purposes internationally, does the man have a fair case?"

An optimist believes we live in the best world possible; a pessimist fears this is true.

Working...