{"entities":{"Q7361121":{"pageid":31518902,"ns":120,"title":"Item:Q7361121","lastrevid":105363101,"modified":"2026-10-07T13:34:45Z","type":"item","id":"Q7361121","labels":{"en":{"language":"en","value":"SAT is Not Solvable in Constant Time"}},"descriptions":{"en":{"language":"en","value":"AFP entry SAT_Not_Const_Time"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0499436a235588c861233b52fea6f358ab266ce2","datavalue":{"value":"https://isa-afp.org/entries/SAT_Not_Const_Time.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361121$0E516E8B-CE14-4A21-BC80-2CD1EF5BB699","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c1d267eea8299129d291a776265fbc3262ab5526","datavalue":{"value":{"time":"+2026-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361121$61A6F991-7B08-4C8E-A683-7E3353FFFF90","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"7c9789720fa439a713eafd635fc379ca547958c6","datavalue":{"value":"Daniel Shea","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361121$EED949DA-8B95-4E02-916F-62BB5E3D93A3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1265e69a86dfb9c7003b5dfb5edcf7fdf0952fe","datavalue":{"value":{"text":"SAT is Not Solvable in Constant Time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361121$67FDCC0F-34F4-425E-8064-6E41536C2EF6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0e7316b0a7e348b23df46bf53c0c39d3de6513f5","datavalue":{"value":"This entry establishes that the Boolean Satisfiability Problem (SAT) cannot be decided by a deterministic Turing machine in constant time \\(O(1)\\). The core of the argument rests on an indistinguishability invariant: a Turing machine bounded by constant time \\(C\\) can only ever read the first \\(C+1\\) cells of its input tape. Consequently, any language decided in constant time must be a prefix language. We then show that SAT is not uniquely determined by any finite prefix, yielding the impossibility result.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361121$97267769-8809-419C-AB8B-BAD1FF1B9398","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361121$6165F094-A16C-4766-A89B-63B0A71FBC83","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"01b7fbcdbb17766b0db638cd8e4d1dc8f5ee62be","datavalue":{"value":{"entity-type":"item","numeric-id":7361443,"id":"Q7361443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361121$72953F25-874D-4AD6-98CC-5CA662D5C2C6","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"73d93a21b0749f7f2c51d7daeb11b162660cd756","datavalue":{"value":{"entity-type":"item","numeric-id":7360784,"id":"Q7360784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361121$6DC9E2CC-CC2D-4C8F-AE9E-D7ACA857795C","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361121$D12DCFF5-E7C4-49C6-876B-3A4F2A1F9A3E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"SAT is Not Solvable in Constant Time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/SAT_is_Not_Solvable_in_Constant_Time"}}}}}