PCP

Question 1

{<P>|there is a match using less than n cards}

Answer 1

determinable, We just try all finite number of possibilities

Question 2

{<P>|there is a match using more than n cards}

Answer 2

Same as PCP, if there is some solution that there is solution with more than n because we can concat solutions.

Question 3

{<P>|there is a match using an even number of cards}

Answer 3

Same as PCP, if there is some solution then we can just concat it with itself, giving us an even number of cards.

Question 4

{<P>|there is a match using an un-even number of cards}

Answer 4

Acceptable: We just test all the un-even options and if we find a solution we stop.
Non determinable: using reduction from PCP

Question 5

{<P>|the alphabet only has one character}

Answer 5

Determinable:
If in all cards the top is shorter than the bottom or the opposite we will return false. else return true, because there is some way to solve this.

Question 6

{<P>|there are no adjecent identical cards}

Answer 6

Acceptable: We just check all the options that satisfy the requirement.
Non-decidable: Reduction from PCP.

Question 7

{<P>|there is a solution that uses all of the cards}

Answer 7

Acceptable: try all the options.
Non-decidable: proof by contraction. If this is solvable, then for the regular PCP problem you could just go over all the sub groups and send them to this problem.

Question 8

{<P>|there is no solution}

Answer 8

Not acceptable: using Post’s theorem. Since PCP is known to not be acceptable, PCP~ has to be as well.