Decidability

srestha asked Dec 12, 2018

335 views

0 votes

Match the following

1.P

2.NP

3.NP-Complete

4. NP-Hard

1.Decidable

2.Undecidable

Theory of Computation
theory-of-computation

+ –

srestha asked Dec 12, 2018

srestha

335 views

See all

4 4 Comments

goxul

commented Dec 12, 2018

All of them are decidable. Undecidable problems have a different way of classification called as arithmetical hierarchy.

See: https://en.wikipedia.org/wiki/Arithmetical_hierarchy

1 votes

ankitgupta.1729

commented Dec 12, 2018

1,2,3 are decidable .. But we can't say anything about NP- Hard..Halting problem is undecidable and it is NP- hard too..3-SAT is NP- hard but it is decidable...

1 votes

air1ankit

commented Dec 12, 2018

https://health.uconn.edu/bioinformatics/wp-content/uploads/sites/162/2017/11/Computation_Complexity_2016.pdf

0 votes

Shubhanshu

commented Dec 12, 2018

####

0 votes

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Voting & Accepting an answer helps improve the community

← Previous Next →

← Previous in category Next in category →

Related questions

1 votes

0 answers

amitarp818 asked Dec 28, 2023

236 views

Decidability
L(M)={0} We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable) I don’t understand why this is not decidable. We can easily create a turing that accepts this language

L(M)={0}We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable)I don’t ...

amitarp818

236 views

amitarp818 asked Dec 28, 2023

Theory of Computation
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages

+ –

0 votes

0 answers

baofbuiafbi asked Nov 14, 2023

144 views

Michael Sipser Decidability Problem
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. L = {M | M is a Turing machine and L(M) ∈ TIME(2^n)}

Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...

baofbuiafbi

144 views

baofbuiafbi asked Nov 14, 2023

Theory of Computation
theory-of-computation
time-complexity
michael-sipser

+ –

0 votes

0 answers

baofbuiafbi asked Nov 14, 2023

143 views

Michael Sipster Decidability Problems
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)

Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)

baofbuiafbi

143 views

baofbuiafbi asked Nov 14, 2023

Theory of Computation
theory-of-computation
michael-sipser
algorithms

+ –

0 votes

1 answer

ajaysoni1924 asked Jul 15, 2019

852 views

Self Doubt: Decidability
$L=\left \{\langle M_{1},M_{2}\rangle \text{ such that L}(M_{1})\prec L(M_{2}) \right \}$ is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \right )$ signifies language $L\left ( M_{1} \right )$ is reducible to $L\left ( M_{2} \right )$

$L=\left \{\langle M_{1},M_{2}\rangle \text{ such that L}(M_{1})\prec L(M_{2}) \right \}$is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \ri...

ajaysoni1924

852 views

ajaysoni1924 asked Jul 15, 2019

Theory of Computation
theory-of-computation
turing-machine
decidability
recursive-and-recursively-enumerable-languages

+ –

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

4 4 Comments reply

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Related questions

4 4 Comments