Some propositional logic questions

[mary]

Hi everyone,

I have a few questions i'm not sure how to do, can someone please help? Thanks!

For Q 1-3, indicate whether it is in NP
1.) Given a graph G(V,E) and an integer k. Does G have at most k different Hamiltonian Cycles?
2.) Given a graph G(V,E) and an integer K. Does G have at least k different Hamiltonian Cycles?
3.) Given a list L of integers of length 2k and an integer x. Are exactly k items of L greater than or equal to x?

I believe both 2. and 3. are in NP while 1. is not. (not so sure)

Q4. Are there any other single propositional connectives that are complete other than nand and nor? Justify your answer.

I think there's none, but how do one go about proving it?

Thank you so much!

[Brightguy]

Sweet, logic and complexity theory.

Remember, a problem is in NP if you can verify the solution in polynomial time. Determining if a graph has a Hamiltonian cycle satisfies this, since given a cycle you can easily check if it meets the requirements. (In fact, the problem is NP-complete.)

Q1 is the complement of Q2 (ok, technically it should be strictly less than) so you can say that it's in coNP. I think your intuition is correct but I'm not sure how you would prove it's not in NP. (Though the ideal solution would show it's in NP by proving P=NP... then you finish the question and get a million dollars. )

Q3 almost seems like a trick question, you can solve it in O(k) so it's trivially in NP.

For Q4, I assume you are limited to only binary connectives? In that case, yes, NAND and NOR are the only ones. Get to work writing out all 16 truth-tables for P and Q... actually, it's not that hard.

Notice that in the 1, 1 row of a truth-table, if the output is a 1, then you no matter how many different crazy combinations of the connective you come up with, the output must always be 1 if you feed it all 1s. Thus, any complete connective must output 0 on inputs 1, 1 (and output 1 on inputs 0, 0 by similar reasoning). That removes 3/4 of the possible truth-tables. The 4 left-over tables are equivalent to NOT(P), NOT(Q), P NAND Q and P NOR Q, but NOT is not complete.