Mixing
![HR Director returning to career after 8 years [duplicate]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjbpfN9tAutmK93bJRC3ZoROZzi2TJDms5n8_qJuhgE0a9b52OOHayv3NGT8igAdFL7byXNst-_1DZK5SjrIJ28_6RQPUpBROqMs5s6jo-ZsjX8kjDwfxJufIitH3TaQRXWaGSQKRQib-f/s72-c/1.jpg)
Proving special case of SAT is in P
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let SAT-100 be the following problem:
Input: Any boolean logic formula
Output: True if there exists a combination of exactly 100 input variables that satisfy the formula.
This is the description of a problem that is appearently in $P$. (old exam question)
I have tried to design an algorithm but I got stuck, so here it goes:
Input: boolean logic formula F
If(count(variables in F)) < 100:
return false
else
# try all combinations of input variables
And here is the problem: building and evaluating all combinations of input variables cant seem to be polynomial because:
$$ n choose 100 = fracn! 100! cdot (n-100)! in mathcalO(n!)
$$
and this nasty factorial cant be bounded with any polinomial that I know of.
I dont think the exam is wrong, so I must have overlooked something.
algorithms satisfiability polynomial-time
edited Sep 3 at 10:58
Filippo De Bortoli
1276
asked Sep 2 at 13:28
zython
217110
add a comment |Â
up vote
2
down vote
favorite
Let SAT-100 be the following problem:
Input: Any boolean logic formula
Output: True if there exists a combination of exactly 100 input variables that satisfy the formula.
This is the description of a problem that is appearently in $P$. (old exam question)
I have tried to design an algorithm but I got stuck, so here it goes:
Input: boolean logic formula F
If(count(variables in F)) < 100:
return false
else
# try all combinations of input variables
And here is the problem: building and evaluating all combinations of input variables cant seem to be polynomial because:
$$ n choose 100 = fracn! 100! cdot (n-100)! in mathcalO(n!)
$$
and this nasty factorial cant be bounded with any polinomial that I know of.
I dont think the exam is wrong, so I must have overlooked something.
algorithms satisfiability polynomial-time
edited Sep 3 at 10:58
Filippo De Bortoli
1276
asked Sep 2 at 13:28
zython
217110
Hint: how many input variable combinations are there and how long does it take to check if each one satisfies the formula or not?
– badroit
Sep 2 at 13:51
What do you mean by a combination of input variables satisfying the formula?
– David Richerby
Sep 2 at 20:54
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let SAT-100 be the following problem:
Input: Any boolean logic formula
Output: True if there exists a combination of exactly 100 input variables that satisfy the formula.
This is the description of a problem that is appearently in $P$. (old exam question)
I have tried to design an algorithm but I got stuck, so here it goes:
Input: boolean logic formula F
If(count(variables in F)) < 100:
return false
else
# try all combinations of input variables
And here is the problem: building and evaluating all combinations of input variables cant seem to be polynomial because:
$$ n choose 100 = fracn! 100! cdot (n-100)! in mathcalO(n!)
$$
and this nasty factorial cant be bounded with any polinomial that I know of.
I dont think the exam is wrong, so I must have overlooked something.
algorithms satisfiability polynomial-time
edited Sep 3 at 10:58
Filippo De Bortoli
1276
asked Sep 2 at 13:28
zython
217110
Let SAT-100 be the following problem:
Input: Any boolean logic formula
Output: True if there exists a combination of exactly 100 input variables that satisfy the formula.
This is the description of a problem that is appearently in $P$. (old exam question)
I have tried to design an algorithm but I got stuck, so here it goes:
Input: boolean logic formula F
If(count(variables in F)) < 100:
return false
else
# try all combinations of input variables
And here is the problem: building and evaluating all combinations of input variables cant seem to be polynomial because:
$$ n choose 100 = fracn! 100! cdot (n-100)! in mathcalO(n!)
$$
and this nasty factorial cant be bounded with any polinomial that I know of.
I dont think the exam is wrong, so I must have overlooked something.
algorithms satisfiability polynomial-time
edited Sep 3 at 10:58
Filippo De Bortoli
1276
asked Sep 2 at 13:28
zython
217110
edited Sep 3 at 10:58
Filippo De Bortoli
1276
edited Sep 3 at 10:58
Filippo De Bortoli
1276
edited Sep 3 at 10:58
Filippo De Bortoli
1276
1276
asked Sep 2 at 13:28
zython
217110
asked Sep 2 at 13:28
zython
217110
asked Sep 2 at 13:28
zython
217110
217110
Hint: how many input variable combinations are there and how long does it take to check if each one satisfies the formula or not?
– badroit
Sep 2 at 13:51
What do you mean by a combination of input variables satisfying the formula?
– David Richerby
Sep 2 at 20:54
add a comment |Â
Hint: how many input variable combinations are there and how long does it take to check if each one satisfies the formula or not?
– badroit
Sep 2 at 13:51
What do you mean by a combination of input variables satisfying the formula?
– David Richerby
Sep 2 at 20:54
Hint: how many input variable combinations are there and how long does it take to check if each one satisfies the formula or not?
– badroit
Sep 2 at 13:51
Hint: how many input variable combinations are there and how long does it take to check if each one satisfies the formula or not?
– badroit
Sep 2 at 13:51
What do you mean by a combination of input variables satisfying the formula?
– David Richerby
Sep 2 at 20:54
What do you mean by a combination of input variables satisfying the formula?
– David Richerby
Sep 2 at 20:54
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
6
down vote
accepted
Note that
$$fracn!(n-100)!100!<fracn!(n-100)!= n cdot (n-1)cdot ldots cdot (n-99)< n^100.$$
Thus, your algorithm runs in polynomial time
answered Sep 2 at 13:57
user3563894
1318
this is just what I was looking for, thank you
– zython
Sep 2 at 13:58
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
Note that
$$fracn!(n-100)!100!<fracn!(n-100)!= n cdot (n-1)cdot ldots cdot (n-99)< n^100.$$
Thus, your algorithm runs in polynomial time
answered Sep 2 at 13:57
user3563894
1318
this is just what I was looking for, thank you
– zython
Sep 2 at 13:58
add a comment |Â
up vote
6
down vote
accepted
Note that
$$fracn!(n-100)!100!<fracn!(n-100)!= n cdot (n-1)cdot ldots cdot (n-99)< n^100.$$
Thus, your algorithm runs in polynomial time
answered Sep 2 at 13:57
user3563894
1318
this is just what I was looking for, thank you
– zython
Sep 2 at 13:58
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
Note that
$$fracn!(n-100)!100!<fracn!(n-100)!= n cdot (n-1)cdot ldots cdot (n-99)< n^100.$$
Thus, your algorithm runs in polynomial time
answered Sep 2 at 13:57
user3563894
1318
Note that
$$fracn!(n-100)!100!<fracn!(n-100)!= n cdot (n-1)cdot ldots cdot (n-99)< n^100.$$
Thus, your algorithm runs in polynomial time
answered Sep 2 at 13:57
user3563894
1318
answered Sep 2 at 13:57
user3563894
1318
answered Sep 2 at 13:57
user3563894
1318
answered Sep 2 at 13:57
user3563894
1318
1318
this is just what I was looking for, thank you
– zython
Sep 2 at 13:58
add a comment |Â
this is just what I was looking for, thank you
– zython
Sep 2 at 13:58
this is just what I was looking for, thank you
– zython
Sep 2 at 13:58
this is just what I was looking for, thank you
– zython
Sep 2 at 13:58
add a comment |Â
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%2f96900%2fproving-special-case-of-sat-is-in-p%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
Hint: how many input variable combinations are there and how long does it take to check if each one satisfies the formula or not?
– badroit
Sep 2 at 13:51
What do you mean by a combination of input variables satisfying the formula?
– David Richerby
Sep 2 at 20:54