-4
$\begingroup$

Please explain to me if this is true or false. I had this in an exam, and I really need to know if I got this correct. I believe it is true because finite problems have finite solutions, which can be done in polynomial time.

$\endgroup$
2
  • $\begingroup$ Are you talking about decision problems? $\endgroup$
    – Steven
    Nov 9, 2023 at 21:24
  • $\begingroup$ What do you mean by finite problem? the one that can be defined in constant number of bits? $\endgroup$ Nov 9, 2023 at 21:25

1 Answer 1

0
$\begingroup$

If by finite problem, you mean a problem with a finite domain, then yes. Such problems are not only in P, but can be done in constant time since you can build a mapping between every possible input and its correct output.

$\endgroup$
3
  • $\begingroup$ I am not sure about constant time, since you would need to read the input to map to the answer correctly. $\endgroup$
    – Nathaniel
    Nov 9, 2023 at 23:01
  • $\begingroup$ @Nathaniel, If we are talking about finite languages, then reading roughly as much input as the length of the longest accepted word (i.e., a constant) suffices. $\endgroup$
    – Steven
    Nov 9, 2023 at 23:58
  • $\begingroup$ @Steven You are right, of course! $\endgroup$
    – Nathaniel
    Nov 10, 2023 at 5:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.