pouët.net

Go to bottom

P-NP problem, TSP

category: offtopic [glöplog]
but WOW! magic uses google to seem smart!
added on the 2012-05-27 18:02:14 by maali maali
what?
genug ist genug hardy.
added on the 2012-05-28 10:18:29 by xTr1m xTr1m
@Adok The method you sketch sounds like the DPLL algorithm (circa the 60's). . For most formula, it will work just fine and fast. But for some instances, it have an exponential runtime. Devising a generator of formula that will take an exponential runtime for that algorithm is a nice exercise left to the reader. Fun fact : there is an infinity of such generators.
@gasman:
you're right about that triangl construction part - i was totally missing it; thanks
added on the 2012-05-28 12:27:13 by rac rac

login

Go to top