Is there any NP-complet problem which is linear on average ? Perhaps
the satisfiability of propositionnal calculus (with Boyer Moore
algorithm) ?
Christophe
–
———————————————————-
Christophe Raffalli
L.F.C.S. (Laboratory for Fundation of Computer Science)
Department of Computer Science, King’s building university
Edinburgh EH9 3JZ
———————————————————-
In article <C76BM3….@dcs.ed.ac.uk> c…@dcs.ed.ac.uk (Christophe Raffalli) writes:
Is there any NP-complet problem which is linear on average ? Perhaps
the satisfiability of propositionnal calculus (with Boyer Moore
algorithm) ?
The following discusses polynomial average time for satisfiability,
under various assumptions about the probability distribution.
PW Purdom, and C Brown: "The pure literal rules and polynomial
average time", SIAM J Comput, 14 (1985) pp 943-953.
It has several other references.
–
Alan Smaill, JANET: A.Sma…@uk.ac.ed
Department of Artificial ARPA: A.Smaill%uk.ac…@nsfnet-relay.ac.uk
Intelligence, UUCP: …!uknet!ed.ac.uk!A.Smaill
Edinburgh University.