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.
2
-
$\begingroup$ Are you talking about decision problems? $\endgroup$– StevenCommented 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$– Inuyasha YagamiCommented Nov 9, 2023 at 21:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ I am not sure about constant time, since you would need to read the input to map to the answer correctly. $\endgroup$ Commented 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$– StevenCommented Nov 9, 2023 at 23:58
-
$\begingroup$ @Steven You are right, of course! $\endgroup$ Commented Nov 10, 2023 at 5:55