Computer Science

« first day (995 days earlier) ← previous day next day → last day (3446 days later) »

Dave

12:20 AM

hey

anyone knows what recursively enumerable languages is called in french

can't find it

Gilles

@Dave langage récursivement énumérable

very easy to find, just look at the translation of the Wikipedia article

3 hours later…

vzn

3:41 AM

sameer gupta is asking me about a 3-SAT → 2-SAT reduction idea on my blog...

re this Q/A

A: 3-sat to 2-sat reduction

one could provably use 2SAT to solve 3SAT problems, ie a reduction, its just that there is not a P-time/space reduction unless P=NP. in other words, converting 3SAT to 2SAT, or reducing 3SAT instance $A$ to 2SAT instance $B$, is indeed possible (using extra 2SAT variables and clauses!), but all k...

anyone else ever seen this idea? doubt its new. whatever....

the basic idea is that SAT is a relation among binary variables.

2SAT can be set up to create the same relation among a set of variables, although possibly with some additional/ auxillary/ "ancilla" variables.

so that a 2SAT formula A is true iff a 3SAT formula B is true, where the A formula has extra variables over the B formula.

but, at the expense of a blowup in the conversion. ie not a PSpace conversion.

(dont know if SG has a login here on stackexchange...?)

vzn

3:57 AM

another idea. maybe not needing extra variables. related to the idea of "functional completeness".

imagine 3SAT defining a set of n-bit vectors as the solution.

corresponding 3SAT formulas exist for all sets of bit vectors.

now, isnt this also true for 2SAT? ie for every set of solution bitvectors for a 3SAT formula, there exists a 2SAT formula with the same solution bitvector set.

7 hours later…