Complexity of n conjuction in basis {v, ¬}
up vote
1
down vote
favorite
Please, tell me how to prove that complexity of x1&x2&...&xn in basis {v,¬} = 2n. It is obvious that complexity <= 2n ¬(¬x1v¬x2v...v¬xn), but how to shom that complexity can not be less?
logic computational-complexity
asked Nov 14 at 21:51
Che4ako
111
add a comment |
up vote
1
down vote
favorite
Please, tell me how to prove that complexity of x1&x2&...&xn in basis {v,¬} = 2n. It is obvious that complexity <= 2n ¬(¬x1v¬x2v...v¬xn), but how to shom that complexity can not be less?
logic computational-complexity
asked Nov 14 at 21:51
Che4ako
111
1
How do you define complexity of a formula?
– Berci
Nov 14 at 22:02
It is number of operations in formula.
– Che4ako
Nov 16 at 6:39
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Please, tell me how to prove that complexity of x1&x2&...&xn in basis {v,¬} = 2n. It is obvious that complexity <= 2n ¬(¬x1v¬x2v...v¬xn), but how to shom that complexity can not be less?
logic computational-complexity
asked Nov 14 at 21:51
Che4ako
111
Please, tell me how to prove that complexity of x1&x2&...&xn in basis {v,¬} = 2n. It is obvious that complexity <= 2n ¬(¬x1v¬x2v...v¬xn), but how to shom that complexity can not be less?
logic computational-complexity
logic computational-complexity
asked Nov 14 at 21:51
Che4ako
111
asked Nov 14 at 21:51
Che4ako
111
asked Nov 14 at 21:51
Che4ako
111
asked Nov 14 at 21:51
Che4ako
111
asked Nov 14 at 21:51
Che4ako
111
111
1
How do you define complexity of a formula?
– Berci
Nov 14 at 22:02
It is number of operations in formula.
– Che4ako
Nov 16 at 6:39
add a comment |
1
How do you define complexity of a formula?
– Berci
Nov 14 at 22:02
It is number of operations in formula.
– Che4ako
Nov 16 at 6:39
1
1
How do you define complexity of a formula?
– Berci
Nov 14 at 22:02
How do you define complexity of a formula?
– Berci
Nov 14 at 22:02
It is number of operations in formula.
– Che4ako
Nov 16 at 6:39
It is number of operations in formula.
– Che4ako
Nov 16 at 6:39
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2998870%2fcomplexity-of-n-conjuction-in-basis-v-%25c2%25ac%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
How do you define complexity of a formula?
– Berci
Nov 14 at 22:02
It is number of operations in formula.
– Che4ako
Nov 16 at 6:39