No code, please. Just explain. Thank you! Question 2: Answer yes or no and Prove

Question

No code, please. Just explain. Thank you!

Question 2: Answer yes or no and Prove or explain precisely why 1. NPC problems are decidable 2. Problems that use an additional space of at most n2 are decidable. Hint: Say that y is written on the tape and the state is q. Also say that later this happens again: y is written on the tape the state is q, and the head in both cases points to the same character. This means an infinite loop. 3. Problems for which the number of possible solution is infinite are not decidable.

Explanation / Answer

1)

There are 2 kinds of problems:

Decidable and non-decidable problems.

Decidable problems:

The problem for which algorithm is exist then it is decidable problem.

Others are non- decidable.

Again these decidable problems are divided into tractable and intractable problems.

Tractable problems:

There exist polynomical bound algorithm for the problem. [ Example, Eulerian tour problem ]

Also called as P problems.

Intractable problem:

These take long time to halt. But, means complexities are high. In laymen language, we can say these are tough problems.

Also called as NP problems.

NP hard problem:

It problem is in NP, and it is reducible to problem A in polynomical time, then A is NP HARD.

NPC: It problem is in NP and NP HARD, then it is NPC.

So, NP and NPH are decidable problems so NPC also decidable.

2) Problems that use an additional space of n^2 are decidable.

There is an infinite space that needs to be explored by an undecidable algorithm. It may or may not halt.

If it has algorithm,

It should use finite steps and finite space too.

Because, if space goes to infinite then algorithm has to infinite to explore that.

So, it is decidable.

3)

problems for which the number of possible solution is infinite are not decidable

Every step in algorithm should be unambiguous and deterministic.

Here 2 cases:

Case 1:

If output is same, but number of possible solutions are more than one to represent this output then it is unambiguous.

SO, it is undecidable.

Case 2:

If it generates different solutions( consequently different outputs) for given input, it comes under undecidable.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.