algorithm - Why do we say that NP complete problems are NP? -


i have gone through links regarding topic still confused why consider np complete np. can verify in polynomial time np complete problems np, have np problems can solved in polynomial time np complete problems can't solved in polynomial time doesn't contradict property of calling np complete problems np?

there's set p of decision problems can solved deterministic turing machine in polynomial time.

then there's set np of decision problems can solved non-deterministic turing machine in polynomial time, i.e. solution can verified in polynomial time given witness string.

a deterministic turing machine can simulate non-deterministic one, know there exponential-time algorithm solve np problems. don't know whether don't in fact have p = np.

an np-complete problem np problem at least hard other np problem. example, sat np-complete because can encode non-deterministic turing machine , solving sat means simulating machine. can show np-completeness of problem decision problem demonstrating known np-complete problem b can reduced in polynomial time. means if can solved in polynomial time, b can solved in polynomial time too, in sense @ least hard b.

but have np problems can solved in polynomial time well

exactly, because p subset of np.

np complete problems can't solved in polynomial time

we don't know sure.

doesn't contradict property of calling np complete problems np

not @ all. yes there problems in np know in p. doesn't mean there no problems in np not in p. of course don't know latter. case every np-complete problem in p, in case p = np.


Comments

Post a Comment

Popular posts from this blog

javascript - Using jquery append to add option values into a select element not working -

i'm looking dynamically populate select element names of items stored array. for reason it's not working , i'm not sure why. html: <div class="col-md-4 col-md-offset-4"> <select class="select1"> </select> , <select class="select2"> </select> </div> note i'm using bootstrap layout. here's jquery i'm using try , populate ".select1" jquery: select: function() { $.each(state.greens, function(index, value) { $(".select1").append("<option value =' " + index + " '>" + state.greens[index].name + "</option>"); }); } note function 'select' stored within object called 'display'. state.greens name of array i'm trying access. so @ end of html page call display.select(); call function. no error messages showing in console. also, saw question: appending
Read more

Android soft keyboard reverts to default keyboard on orientation change -

i'm building android soft keyboard , can't seem fix bug - have arabic , qwerty keyboard , when rotate device on qwerty keyboard (or arabic shift), it's if program has "restarted" , becomes arabic keyboard without shift. the onsaveinstancestate(bundle savedinstancestate) not work because application not extend activity inputmethodservice . i put following in android manifest android:configchanges="keyboard|keyboardhidden|orientation" android:windowsoftinputmode="stateunchanged|adjustresize"> i tried using @override public void onconfigurationchanged(configuration newconfig) { super.onconfigurationchanged(newconfig); log.i(mydebug, "config changed " + currentkeyboard.equals(qwerty)); } however, currentkeyboard.equals(qwerty)) results false , made sure true before orientation change. any appreciated. i think applications fault. if application restarting on orientation change
Read more

jquery - javascript onscroll fade same class but with different div -

i new @ javascript , want learn new. there wrong code : why div fades @ same time. i want ask how fade different div s same class name.can me , explain me. thanks in advance. javascript: $(window).scroll(function(){ if ($( "div.fade" ).offset().top - $(window).scrolltop() <= 100){ $('.fade').addclass( "fade-in"); } else { $('.fade').removeclass("fade-in"); } }); here jsfiddle onscroll = function () { var scrolltop = $(this).scrolltop() ; $("div.fade").each(function(){ if(($(this).offset().top - scrolltop) <= 100){ $(this).toggleclass("fade-in"); } }) }
Read more