Does there exist a more optimum algorithm to solve every problem than brute force (or an equivalent)?

A brute force algorithm for the purpose of this question is defined as an algorithm of time complexity $N^*$, there $N^*$ is the cardinality of the set of all possible solutions.

  • $\begingroup$ Brute force is just a general strategy of search by exhausion on set of possible solutions. This set is subjective depending on how insightful you are. Thus, brute force algorithm is not formally defined on all problems and the OP question can't be answered. $\endgroup$ – Apiwat Chantawibul Jul 6 '17 at 10:06
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Jul 6 '17 at 19:04
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jul 6 '17 at 19:04

No. For every decision problem, the cardinality of the set of possible solutions is two: "yes" and "no". It is not the case that all problems can be solved in constant time.

  • $\begingroup$ So, you mean that there exist problems which have brute force runtime as lower runtime bound? $\endgroup$ – rus9384 Jul 7 '17 at 9:09
  • $\begingroup$ @rus9384 I mostly mean that the definition of "brute force" given in the question doesn't make a lot of sense. $\endgroup$ – David Richerby Jul 7 '17 at 9:14
  • $\begingroup$ Yeah, but in terms of functional problems it's be OK. $\endgroup$ – rus9384 Jul 7 '17 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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