Bissoy.com
Doctors Medicines MCQs Q&A

Which of the following problem is not NP complete but undecidable?

Which of the following problem is not NP complete but undecidable? Correct Answer Halting Problem

  • The halting problem is NP-Hard, not NP-Complete, but is undecidable. Hence option 2 is correct.
  • Hamiltonian circuit, bin packing, partition problems are NP-complete problems.
Important Points 
  • The halting problem is undecidable over Turing machines.
  • The halting problem is recursively enumerable but not recursive. we can run the Turing Machine and accept if the machine halts, hence it is recursively enumerable.

Related Questions

Which of following problems are undecidable? I. Membership problem in context-free languages II. Whether a given context-free language is regular III. Whether a finite state automation halts on all inputs IV. Membership problem for type 0 languages
Given below are two statements: Statement I: The problem "Is L1 ∧ L2 = ϕ?" is undecidable for context sensitive languages L1 and L2. Statement II: The problem "Is WϵL?" is decidable for context sensitive language L, (where W is a string). In the light of the above statements, choose the correct answer from the options given below
The following sentences form a paragraph. These four parts are numbered as P, Q, R and S. They are not given in their proper order. Read the sentences and choose the alternative that arranges them in correct order. P. Inverse problem refers to the scientific problem of estimating the different causes that led to a particular outcome.  Q. This is in contrast to the forward or the direct problem where scientists try to find the outcome that results from a series of causes. R. A scientist observing a photograph, for instance, would be faced with the inverse problem while trying to figure out the various causal factors that combined to form the final photograph. The inverse problem is applied to understand processes in a wide variety of sciences. S. Scientists trying to understand an observation may at times have to work backwards to estimate the causal factors behind it.
Read the passage carefully and choose the best answer to each question out of the four alternatives andclick the button corresponding to it.
There is a time in every man's education when he arrives at the conviction that envy is ignorance; that imitation is suicide; that he must take himself for better, forworse, as his portion; that though the wide universe is full of good, no kernel of nourishing corn can come to him but through his toil bestowed on that plot of groundwhich is given to him to till. The power which resides in him is new in nature, and none but he knows what that is which he can do, nor does he know until he hastried. Not for nothing one face, one character, one fact, makes much impression on him, and another none. This sculpture in the memory is not without pre-established harmony. The eye was placed where one ray should fall, that it might testify of that particular ray. We but half express ourselves, and are ashamed ofthat divine idea which each of us represents. It may be safely trusted as proportionate and of good issues, so it be faithfully imparted, but God will not have his workmade manifest by cowards. A man is relieved and gay when he has put his heart into his work and has done his best; but what he has said or done otherwise, shallgive him no peace. It is a deliverance which does not deliver. In the attempt his genius deserts him; no muse befriends; no invention, no hope. According to the author, God is not looking for _____ to manifest his works.
A, B and C can together complete a work in 20 days. On the other hand, B and C can together complete the work in 30 days, while C can complete the work alone in 50 days. If A left when the work was 20% complete, while B left when the work was 50% complete, and C completed rest of the work alone, in how many days will the work be complete?
Read the passage carefully and choose the best answer to each question out of the four alternatives andclick the button corresponding to it.
There is a time in every man's education when he arrives at the conviction that envy is ignorance; that imitation is suicide; that he must take himself for better, forworse, as his portion; that though the wide universe is full of good, no kernel of nourishing corn can come to him but through his toil bestowed on that plot of groundwhich is given to him to till. The power which resides in him is new in nature, and none but he knows what that is which he can do, nor does he know until he hastried. Not for nothing one face, one character, one fact, makes much impression on him, and another none. This sculpture in the memory is not without pre-established harmony. The eye was placed where one ray should fall, that it might testify of that particular ray. We but half express ourselves, and are ashamed ofthat divine idea which each of us represents. It may be safely trusted as proportionate and of good issues, so it be faithfully imparted, but God will not have his workmade manifest by cowards. A man is relieved and gay when he has put his heart into his work and has done his best; but what he has said or done otherwise, shallgive him no peace. It is a deliverance which does not deliver. In the attempt his genius deserts him; no muse befriends; no invention, no hope. Which of the following does the author appear to highlight in this essay?
Given below are two quantities named A and B. Based on the given information, you have to determine the relation between the two quantities. You should use the given data and your knowledge of Mathematics to choose between the possible answers. Quantity A: M and N can complete the work in 10 and 20 days respectively. They started doing work together but after 4 days M left the work. In what time N can complete the remaining work? Quantity B: A and B can together complete the work in 12 days. A alone can complete the work in 30 days. If B works for first 4 days alone and then A joins the work, in how many days remaining work will be complete?
Each of the following problem has a question and two statements which are labeled 1. and. Use the data given in 1. and 2. to decide whether the statements are sufficient to answer the question.Select one of the following . a.Statements (1) ALONE is sufficient,but (2) ALONE is not sufficient. b.Statements (2) ALONE is sufficient,but (1) ALONE is not sufficient. c. Both statement TOGETHER are sufficient but statement alone is sufficient . A fly crawls around the outside of a circle once.A second fly crawls around the outside of a square once.Which fly travels further ? (1) The diagonal of the square is equal to the diagonal of the circle.(2) The fly crawling around the circle took more time to complete has journey than the fly cawing around the square.
Read the passage carefully and choose the best answer to each question out of the four alternatives andclick the button corresponding to it.
There is a time in every man's education when he arrives at the conviction that envy is ignorance; that imitation is suicide; that he must take himself for better, forworse, as his portion; that though the wide universe is full of good, no kernel of nourishing corn can come to him but through his toil bestowed on that plot of groundwhich is given to him to till. The power which resides in him is new in nature, and none but he knows what that is which he can do, nor does he know until he hastried. Not for nothing one face, one character, one fact, makes much impression on him, and another none. This sculpture in the memory is not without pre-established harmony. The eye was placed where one ray should fall, that it might testify of that particular ray. We but half express ourselves, and are ashamed ofthat divine idea which each of us represents. It may be safely trusted as proportionate and of good issues, so it be faithfully imparted, but God will not have his workmade manifest by cowards. A man is relieved and gay when he has put his heart into his work and has done his best; but what he has said or done otherwise, shallgive him no peace. It is a deliverance which does not deliver. In the attempt his genius deserts him; no muse befriends; no invention, no hope. What is that which only the person himself knows and must act in order to discover it?
Read the passage carefully and choose the best answer to each question out of the four alternatives andclick the button corresponding to it.
There is a time in every man's education when he arrives at the conviction that envy is ignorance; that imitation is suicide; that he must take himself for better, forworse, as his portion; that though the wide universe is full of good, no kernel of nourishing corn can come to him but through his toil bestowed on that plot of groundwhich is given to him to till. The power which resides in him is new in nature, and none but he knows what that is which he can do, nor does he know until he hastried. Not for nothing one face, one character, one fact, makes much impression on him, and another none. This sculpture in the memory is not without pre-established harmony. The eye was placed where one ray should fall, that it might testify of that particular ray. We but half express ourselves, and are ashamed ofthat divine idea which each of us represents. It may be safely trusted as proportionate and of good issues, so it be faithfully imparted, but God will not have his workmade manifest by cowards. A man is relieved and gay when he has put his heart into his work and has done his best; but what he has said or done otherwise, shallgive him no peace. It is a deliverance which does not deliver. In the attempt his genius deserts him; no muse befriends; no invention, no hope. When is a man relieved and gay?