Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?
DEAL: For $25 - Add A Second Phone Number To Your Smartphone for life! Use promo code SLASHDOT25. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. Check out the new SourceForge HTML5 Internet speed test! ×

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

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).


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

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?"

Slashdot Top Deals

Riches cover a multitude of woes. -- Menander