Mixing
Why SAT Requires A Non-determinstic Algorithm?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I am getting started to understand the probelm of Satisfiability and i am reading (Computers and Intractability: A Guide to the Theory of NP-Completeness).
I do understand the difference between a Deterministic and Non-Deterministic Algorithm, however i don't understand why SAT requires a Non-Determinsitic Algorithm ? Why not a Deterministic Algorithm ?
How do we know for sure that a problem requires a Deterministic or Non-Deterministic Algorith that solves it ? (if it was solvable, i,e. not undecidable problem).
satisfiability decision-problem nondeterminism
asked 4 hours ago
Jacob Billerchy
61
New contributor
Jacob Billerchy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
favorite
I am getting started to understand the probelm of Satisfiability and i am reading (Computers and Intractability: A Guide to the Theory of NP-Completeness).
I do understand the difference between a Deterministic and Non-Deterministic Algorithm, however i don't understand why SAT requires a Non-Determinsitic Algorithm ? Why not a Deterministic Algorithm ?
How do we know for sure that a problem requires a Deterministic or Non-Deterministic Algorith that solves it ? (if it was solvable, i,e. not undecidable problem).
satisfiability decision-problem nondeterminism
asked 4 hours ago
Jacob Billerchy
61
New contributor
Jacob Billerchy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am getting started to understand the probelm of Satisfiability and i am reading (Computers and Intractability: A Guide to the Theory of NP-Completeness).
I do understand the difference between a Deterministic and Non-Deterministic Algorithm, however i don't understand why SAT requires a Non-Determinsitic Algorithm ? Why not a Deterministic Algorithm ?
How do we know for sure that a problem requires a Deterministic or Non-Deterministic Algorith that solves it ? (if it was solvable, i,e. not undecidable problem).
satisfiability decision-problem nondeterminism
asked 4 hours ago
Jacob Billerchy
61
New contributor
Jacob Billerchy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I am getting started to understand the probelm of Satisfiability and i am reading (Computers and Intractability: A Guide to the Theory of NP-Completeness).
I do understand the difference between a Deterministic and Non-Deterministic Algorithm, however i don't understand why SAT requires a Non-Determinsitic Algorithm ? Why not a Deterministic Algorithm ?
How do we know for sure that a problem requires a Deterministic or Non-Deterministic Algorith that solves it ? (if it was solvable, i,e. not undecidable problem).
satisfiability decision-problem nondeterminism
satisfiability decision-problem nondeterminism
asked 4 hours ago
Jacob Billerchy
61
New contributor
Jacob Billerchy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Jacob Billerchy
61
New contributor
Jacob Billerchy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Jacob Billerchy
61
New contributor
Jacob Billerchy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Jacob Billerchy
61
asked 4 hours ago
Jacob Billerchy
61
61
New contributor
Jacob Billerchy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Jacob Billerchy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Jacob Billerchy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
Any decidable problem can be solved by a deterministic algorithm. The thing about SAT (and any other NP-complete problem) is that we don't know any efficient deterministic algorithm that solves it, and we think there might not even be one.
answered 2 hours ago
David Richerby
61.7k1594179
So, Assuming there is an efficient deterministic & non-deterministic algorithm for SAT, and there exists multiple Accepting Solutions for a given Boolean Formula. Are we interested in having all the (Accepting States) therefore use the nondeterministic algorithm or we only (any) accepting state therefore use the determinsitc algorithm ?
– Jacob Billerchy
55 mins ago
The deterministic nature of algorithm has nothing to do with how many solutions we want. Also, I don't think we ever need many solutions for SAT. We are only interested in whether it is satisfiable or not.
– Sandro LovniÄÂki
48 mins ago
@SandroLovniÄÂki Yes i understand that a single solution will tell us if the Boolean Formula evalutes to true or false but what if we later include constraints to choose a solution among the solutions of the given Boolean Formula, wouldn't that require listing all the solutions ?
– Jacob Billerchy
1 min ago
add a comment |Â
up vote
2
down vote
It is not true that it requires a non-deterministic algorithm.
You are right; if it is solvable, it should be solvable by a deterministic algorithm. And it is. This deterministic algorithm needs exponential number of steps (with respect to number of propositional variables $n$) because only known general case approach so far is to test all combinations of truth values of propositional variables, and we have $2^n$ possible combinations (rows of a truth table).
However, we can (theoretically) solve it with a non-deterministic algorithm in polynomial time which is how a class of NP problems is defined. This is where your confusion, and maybe a bad choice of words in the literature, probably comes from.
All non-deterministic algorithms can be simulated by a deterministic algorithm. In fact, all that is computable can be computed with a deterministic algorithm. It is just the time complexity that varies.
answered 2 hours ago
Sandro LovniÄÂki
445113
So how can we distinguish between an implentation of a non-deterministic algorithm simulated on a deterministic algorithm and another (pure) deterministic algorithm ?
– Jacob Billerchy
1 hour ago
Most formally, we cannot. Detecting equality (or any non-trivial property) of algorithms is undecidable. But why would you do that? We write algorithms, therefore we know what we meant for it to do. I don't think there will be a situation that an algorithm pops into existance and asks you to figure out what it is :)
– Sandro LovniÄÂki
1 hour ago
Specifically, in this case, (pure) deterministic algorithm will be implemented similarly like a deterministic algorithm simulating non-deterministic algorithm. (pure) needs to test all $2^n$ possibilities and simulation needs to simulate all non-deterministic branchings. Non-deterministic algorithm still goes through all $2^n$ possibilities, it just does many at once. And I repeat, this is theoretical. If we had real (physicaly working) non-deterministic algorithms, $P neq NP$ would not be a problem of major concern.
– Sandro LovniÄÂki
57 mins ago
Because the Deterministic (D) & Non-Determinsitic (ND) concepts are confusing. My understanding is that D will reach an (Accept / Reject) state, while a ND algorithm will have (if exists) mulitple states of (Accept / Reject). When a ND is simulated on D it will show mulitple states of (Accept / Reject), how come that D shows mulitple (Accept / Reject) states, that will contradict its defination not have a single (Accept / Reject) state ? Or is it the case that those mulitple states of (Accept / Reject) are the equivalent of the (Accept / Reject) state of the simulated D ?
– Jacob Billerchy
6 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Any decidable problem can be solved by a deterministic algorithm. The thing about SAT (and any other NP-complete problem) is that we don't know any efficient deterministic algorithm that solves it, and we think there might not even be one.
answered 2 hours ago
David Richerby
61.7k1594179
So, Assuming there is an efficient deterministic & non-deterministic algorithm for SAT, and there exists multiple Accepting Solutions for a given Boolean Formula. Are we interested in having all the (Accepting States) therefore use the nondeterministic algorithm or we only (any) accepting state therefore use the determinsitc algorithm ?
– Jacob Billerchy
55 mins ago
The deterministic nature of algorithm has nothing to do with how many solutions we want. Also, I don't think we ever need many solutions for SAT. We are only interested in whether it is satisfiable or not.
– Sandro LovniÄÂki
48 mins ago
@SandroLovniÄÂki Yes i understand that a single solution will tell us if the Boolean Formula evalutes to true or false but what if we later include constraints to choose a solution among the solutions of the given Boolean Formula, wouldn't that require listing all the solutions ?
– Jacob Billerchy
1 min ago
add a comment |Â
up vote
2
down vote
Any decidable problem can be solved by a deterministic algorithm. The thing about SAT (and any other NP-complete problem) is that we don't know any efficient deterministic algorithm that solves it, and we think there might not even be one.
answered 2 hours ago
David Richerby
61.7k1594179
So, Assuming there is an efficient deterministic & non-deterministic algorithm for SAT, and there exists multiple Accepting Solutions for a given Boolean Formula. Are we interested in having all the (Accepting States) therefore use the nondeterministic algorithm or we only (any) accepting state therefore use the determinsitc algorithm ?
– Jacob Billerchy
55 mins ago
The deterministic nature of algorithm has nothing to do with how many solutions we want. Also, I don't think we ever need many solutions for SAT. We are only interested in whether it is satisfiable or not.
– Sandro LovniÄÂki
48 mins ago
@SandroLovniÄÂki Yes i understand that a single solution will tell us if the Boolean Formula evalutes to true or false but what if we later include constraints to choose a solution among the solutions of the given Boolean Formula, wouldn't that require listing all the solutions ?
– Jacob Billerchy
1 min ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Any decidable problem can be solved by a deterministic algorithm. The thing about SAT (and any other NP-complete problem) is that we don't know any efficient deterministic algorithm that solves it, and we think there might not even be one.
answered 2 hours ago
David Richerby
61.7k1594179
Any decidable problem can be solved by a deterministic algorithm. The thing about SAT (and any other NP-complete problem) is that we don't know any efficient deterministic algorithm that solves it, and we think there might not even be one.
answered 2 hours ago
David Richerby
61.7k1594179
answered 2 hours ago
David Richerby
61.7k1594179
answered 2 hours ago
David Richerby
61.7k1594179
answered 2 hours ago
David Richerby
61.7k1594179
61.7k1594179
So, Assuming there is an efficient deterministic & non-deterministic algorithm for SAT, and there exists multiple Accepting Solutions for a given Boolean Formula. Are we interested in having all the (Accepting States) therefore use the nondeterministic algorithm or we only (any) accepting state therefore use the determinsitc algorithm ?
– Jacob Billerchy
55 mins ago
The deterministic nature of algorithm has nothing to do with how many solutions we want. Also, I don't think we ever need many solutions for SAT. We are only interested in whether it is satisfiable or not.
– Sandro LovniÄÂki
48 mins ago
@SandroLovniÄÂki Yes i understand that a single solution will tell us if the Boolean Formula evalutes to true or false but what if we later include constraints to choose a solution among the solutions of the given Boolean Formula, wouldn't that require listing all the solutions ?
– Jacob Billerchy
1 min ago
add a comment |Â
So, Assuming there is an efficient deterministic & non-deterministic algorithm for SAT, and there exists multiple Accepting Solutions for a given Boolean Formula. Are we interested in having all the (Accepting States) therefore use the nondeterministic algorithm or we only (any) accepting state therefore use the determinsitc algorithm ?
– Jacob Billerchy
55 mins ago
The deterministic nature of algorithm has nothing to do with how many solutions we want. Also, I don't think we ever need many solutions for SAT. We are only interested in whether it is satisfiable or not.
– Sandro LovniÄÂki
48 mins ago
@SandroLovniÄÂki Yes i understand that a single solution will tell us if the Boolean Formula evalutes to true or false but what if we later include constraints to choose a solution among the solutions of the given Boolean Formula, wouldn't that require listing all the solutions ?
– Jacob Billerchy
1 min ago
So, Assuming there is an efficient deterministic & non-deterministic algorithm for SAT, and there exists multiple Accepting Solutions for a given Boolean Formula. Are we interested in having all the (Accepting States) therefore use the nondeterministic algorithm or we only (any) accepting state therefore use the determinsitc algorithm ?
– Jacob Billerchy
55 mins ago
So, Assuming there is an efficient deterministic & non-deterministic algorithm for SAT, and there exists multiple Accepting Solutions for a given Boolean Formula. Are we interested in having all the (Accepting States) therefore use the nondeterministic algorithm or we only (any) accepting state therefore use the determinsitc algorithm ?
– Jacob Billerchy
55 mins ago
The deterministic nature of algorithm has nothing to do with how many solutions we want. Also, I don't think we ever need many solutions for SAT. We are only interested in whether it is satisfiable or not.
– Sandro LovniÄÂki
48 mins ago
The deterministic nature of algorithm has nothing to do with how many solutions we want. Also, I don't think we ever need many solutions for SAT. We are only interested in whether it is satisfiable or not.
– Sandro LovniÄÂki
48 mins ago
@SandroLovniÄÂki Yes i understand that a single solution will tell us if the Boolean Formula evalutes to true or false but what if we later include constraints to choose a solution among the solutions of the given Boolean Formula, wouldn't that require listing all the solutions ?
– Jacob Billerchy
1 min ago
@SandroLovniÄÂki Yes i understand that a single solution will tell us if the Boolean Formula evalutes to true or false but what if we later include constraints to choose a solution among the solutions of the given Boolean Formula, wouldn't that require listing all the solutions ?
– Jacob Billerchy
1 min ago
add a comment |Â
up vote
2
down vote
It is not true that it requires a non-deterministic algorithm.
You are right; if it is solvable, it should be solvable by a deterministic algorithm. And it is. This deterministic algorithm needs exponential number of steps (with respect to number of propositional variables $n$) because only known general case approach so far is to test all combinations of truth values of propositional variables, and we have $2^n$ possible combinations (rows of a truth table).
However, we can (theoretically) solve it with a non-deterministic algorithm in polynomial time which is how a class of NP problems is defined. This is where your confusion, and maybe a bad choice of words in the literature, probably comes from.
All non-deterministic algorithms can be simulated by a deterministic algorithm. In fact, all that is computable can be computed with a deterministic algorithm. It is just the time complexity that varies.
answered 2 hours ago
Sandro LovniÄÂki
445113
So how can we distinguish between an implentation of a non-deterministic algorithm simulated on a deterministic algorithm and another (pure) deterministic algorithm ?
– Jacob Billerchy
1 hour ago
Most formally, we cannot. Detecting equality (or any non-trivial property) of algorithms is undecidable. But why would you do that? We write algorithms, therefore we know what we meant for it to do. I don't think there will be a situation that an algorithm pops into existance and asks you to figure out what it is :)
– Sandro LovniÄÂki
1 hour ago
Specifically, in this case, (pure) deterministic algorithm will be implemented similarly like a deterministic algorithm simulating non-deterministic algorithm. (pure) needs to test all $2^n$ possibilities and simulation needs to simulate all non-deterministic branchings. Non-deterministic algorithm still goes through all $2^n$ possibilities, it just does many at once. And I repeat, this is theoretical. If we had real (physicaly working) non-deterministic algorithms, $P neq NP$ would not be a problem of major concern.
– Sandro LovniÄÂki
57 mins ago
Because the Deterministic (D) & Non-Determinsitic (ND) concepts are confusing. My understanding is that D will reach an (Accept / Reject) state, while a ND algorithm will have (if exists) mulitple states of (Accept / Reject). When a ND is simulated on D it will show mulitple states of (Accept / Reject), how come that D shows mulitple (Accept / Reject) states, that will contradict its defination not have a single (Accept / Reject) state ? Or is it the case that those mulitple states of (Accept / Reject) are the equivalent of the (Accept / Reject) state of the simulated D ?
– Jacob Billerchy
6 mins ago
add a comment |Â
up vote
2
down vote
It is not true that it requires a non-deterministic algorithm.
You are right; if it is solvable, it should be solvable by a deterministic algorithm. And it is. This deterministic algorithm needs exponential number of steps (with respect to number of propositional variables $n$) because only known general case approach so far is to test all combinations of truth values of propositional variables, and we have $2^n$ possible combinations (rows of a truth table).
However, we can (theoretically) solve it with a non-deterministic algorithm in polynomial time which is how a class of NP problems is defined. This is where your confusion, and maybe a bad choice of words in the literature, probably comes from.
All non-deterministic algorithms can be simulated by a deterministic algorithm. In fact, all that is computable can be computed with a deterministic algorithm. It is just the time complexity that varies.
answered 2 hours ago
Sandro LovniÄÂki
445113
So how can we distinguish between an implentation of a non-deterministic algorithm simulated on a deterministic algorithm and another (pure) deterministic algorithm ?
– Jacob Billerchy
1 hour ago
Most formally, we cannot. Detecting equality (or any non-trivial property) of algorithms is undecidable. But why would you do that? We write algorithms, therefore we know what we meant for it to do. I don't think there will be a situation that an algorithm pops into existance and asks you to figure out what it is :)
– Sandro LovniÄÂki
1 hour ago
Specifically, in this case, (pure) deterministic algorithm will be implemented similarly like a deterministic algorithm simulating non-deterministic algorithm. (pure) needs to test all $2^n$ possibilities and simulation needs to simulate all non-deterministic branchings. Non-deterministic algorithm still goes through all $2^n$ possibilities, it just does many at once. And I repeat, this is theoretical. If we had real (physicaly working) non-deterministic algorithms, $P neq NP$ would not be a problem of major concern.
– Sandro LovniÄÂki
57 mins ago
Because the Deterministic (D) & Non-Determinsitic (ND) concepts are confusing. My understanding is that D will reach an (Accept / Reject) state, while a ND algorithm will have (if exists) mulitple states of (Accept / Reject). When a ND is simulated on D it will show mulitple states of (Accept / Reject), how come that D shows mulitple (Accept / Reject) states, that will contradict its defination not have a single (Accept / Reject) state ? Or is it the case that those mulitple states of (Accept / Reject) are the equivalent of the (Accept / Reject) state of the simulated D ?
– Jacob Billerchy
6 mins ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
It is not true that it requires a non-deterministic algorithm.
You are right; if it is solvable, it should be solvable by a deterministic algorithm. And it is. This deterministic algorithm needs exponential number of steps (with respect to number of propositional variables $n$) because only known general case approach so far is to test all combinations of truth values of propositional variables, and we have $2^n$ possible combinations (rows of a truth table).
However, we can (theoretically) solve it with a non-deterministic algorithm in polynomial time which is how a class of NP problems is defined. This is where your confusion, and maybe a bad choice of words in the literature, probably comes from.
All non-deterministic algorithms can be simulated by a deterministic algorithm. In fact, all that is computable can be computed with a deterministic algorithm. It is just the time complexity that varies.
answered 2 hours ago
Sandro LovniÄÂki
445113
It is not true that it requires a non-deterministic algorithm.
You are right; if it is solvable, it should be solvable by a deterministic algorithm. And it is. This deterministic algorithm needs exponential number of steps (with respect to number of propositional variables $n$) because only known general case approach so far is to test all combinations of truth values of propositional variables, and we have $2^n$ possible combinations (rows of a truth table).
However, we can (theoretically) solve it with a non-deterministic algorithm in polynomial time which is how a class of NP problems is defined. This is where your confusion, and maybe a bad choice of words in the literature, probably comes from.
All non-deterministic algorithms can be simulated by a deterministic algorithm. In fact, all that is computable can be computed with a deterministic algorithm. It is just the time complexity that varies.
answered 2 hours ago
Sandro LovniÄÂki
445113
edited 2 hours ago
answered 2 hours ago
Sandro LovniÄÂki
445113
answered 2 hours ago
Sandro LovniÄÂki
445113
answered 2 hours ago
Sandro LovniÄÂki
445113
445113
So how can we distinguish between an implentation of a non-deterministic algorithm simulated on a deterministic algorithm and another (pure) deterministic algorithm ?
– Jacob Billerchy
1 hour ago
Most formally, we cannot. Detecting equality (or any non-trivial property) of algorithms is undecidable. But why would you do that? We write algorithms, therefore we know what we meant for it to do. I don't think there will be a situation that an algorithm pops into existance and asks you to figure out what it is :)
– Sandro LovniÄÂki
1 hour ago
Specifically, in this case, (pure) deterministic algorithm will be implemented similarly like a deterministic algorithm simulating non-deterministic algorithm. (pure) needs to test all $2^n$ possibilities and simulation needs to simulate all non-deterministic branchings. Non-deterministic algorithm still goes through all $2^n$ possibilities, it just does many at once. And I repeat, this is theoretical. If we had real (physicaly working) non-deterministic algorithms, $P neq NP$ would not be a problem of major concern.
– Sandro LovniÄÂki
57 mins ago
Because the Deterministic (D) & Non-Determinsitic (ND) concepts are confusing. My understanding is that D will reach an (Accept / Reject) state, while a ND algorithm will have (if exists) mulitple states of (Accept / Reject). When a ND is simulated on D it will show mulitple states of (Accept / Reject), how come that D shows mulitple (Accept / Reject) states, that will contradict its defination not have a single (Accept / Reject) state ? Or is it the case that those mulitple states of (Accept / Reject) are the equivalent of the (Accept / Reject) state of the simulated D ?
– Jacob Billerchy
6 mins ago
add a comment |Â
So how can we distinguish between an implentation of a non-deterministic algorithm simulated on a deterministic algorithm and another (pure) deterministic algorithm ?
– Jacob Billerchy
1 hour ago
Most formally, we cannot. Detecting equality (or any non-trivial property) of algorithms is undecidable. But why would you do that? We write algorithms, therefore we know what we meant for it to do. I don't think there will be a situation that an algorithm pops into existance and asks you to figure out what it is :)
– Sandro LovniÄÂki
1 hour ago
Specifically, in this case, (pure) deterministic algorithm will be implemented similarly like a deterministic algorithm simulating non-deterministic algorithm. (pure) needs to test all $2^n$ possibilities and simulation needs to simulate all non-deterministic branchings. Non-deterministic algorithm still goes through all $2^n$ possibilities, it just does many at once. And I repeat, this is theoretical. If we had real (physicaly working) non-deterministic algorithms, $P neq NP$ would not be a problem of major concern.
– Sandro LovniÄÂki
57 mins ago
Because the Deterministic (D) & Non-Determinsitic (ND) concepts are confusing. My understanding is that D will reach an (Accept / Reject) state, while a ND algorithm will have (if exists) mulitple states of (Accept / Reject). When a ND is simulated on D it will show mulitple states of (Accept / Reject), how come that D shows mulitple (Accept / Reject) states, that will contradict its defination not have a single (Accept / Reject) state ? Or is it the case that those mulitple states of (Accept / Reject) are the equivalent of the (Accept / Reject) state of the simulated D ?
– Jacob Billerchy
6 mins ago
So how can we distinguish between an implentation of a non-deterministic algorithm simulated on a deterministic algorithm and another (pure) deterministic algorithm ?
– Jacob Billerchy
1 hour ago
So how can we distinguish between an implentation of a non-deterministic algorithm simulated on a deterministic algorithm and another (pure) deterministic algorithm ?
– Jacob Billerchy
1 hour ago
Most formally, we cannot. Detecting equality (or any non-trivial property) of algorithms is undecidable. But why would you do that? We write algorithms, therefore we know what we meant for it to do. I don't think there will be a situation that an algorithm pops into existance and asks you to figure out what it is :)
– Sandro LovniÄÂki
1 hour ago
Most formally, we cannot. Detecting equality (or any non-trivial property) of algorithms is undecidable. But why would you do that? We write algorithms, therefore we know what we meant for it to do. I don't think there will be a situation that an algorithm pops into existance and asks you to figure out what it is :)
– Sandro LovniÄÂki
1 hour ago
Specifically, in this case, (pure) deterministic algorithm will be implemented similarly like a deterministic algorithm simulating non-deterministic algorithm. (pure) needs to test all $2^n$ possibilities and simulation needs to simulate all non-deterministic branchings. Non-deterministic algorithm still goes through all $2^n$ possibilities, it just does many at once. And I repeat, this is theoretical. If we had real (physicaly working) non-deterministic algorithms, $P neq NP$ would not be a problem of major concern.
– Sandro LovniÄÂki
57 mins ago
Specifically, in this case, (pure) deterministic algorithm will be implemented similarly like a deterministic algorithm simulating non-deterministic algorithm. (pure) needs to test all $2^n$ possibilities and simulation needs to simulate all non-deterministic branchings. Non-deterministic algorithm still goes through all $2^n$ possibilities, it just does many at once. And I repeat, this is theoretical. If we had real (physicaly working) non-deterministic algorithms, $P neq NP$ would not be a problem of major concern.
– Sandro LovniÄÂki
57 mins ago
Because the Deterministic (D) & Non-Determinsitic (ND) concepts are confusing. My understanding is that D will reach an (Accept / Reject) state, while a ND algorithm will have (if exists) mulitple states of (Accept / Reject). When a ND is simulated on D it will show mulitple states of (Accept / Reject), how come that D shows mulitple (Accept / Reject) states, that will contradict its defination not have a single (Accept / Reject) state ? Or is it the case that those mulitple states of (Accept / Reject) are the equivalent of the (Accept / Reject) state of the simulated D ?
– Jacob Billerchy
6 mins ago
Because the Deterministic (D) & Non-Determinsitic (ND) concepts are confusing. My understanding is that D will reach an (Accept / Reject) state, while a ND algorithm will have (if exists) mulitple states of (Accept / Reject). When a ND is simulated on D it will show mulitple states of (Accept / Reject), how come that D shows mulitple (Accept / Reject) states, that will contradict its defination not have a single (Accept / Reject) state ? Or is it the case that those mulitple states of (Accept / Reject) are the equivalent of the (Accept / Reject) state of the simulated D ?
– Jacob Billerchy
6 mins ago
add a comment |Â
Jacob Billerchy is a new contributor. Be nice, and check out our Code of Conduct.
Jacob Billerchy is a new contributor. Be nice, and check out our Code of Conduct.
Jacob Billerchy is a new contributor. Be nice, and check out our Code of Conduct.
Jacob Billerchy is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f97583%2fwhy-sat-requires-a-non-determinstic-algorithm%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password