0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Jul 6, 2017 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
    Commented Jul 6, 2017 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
    Commented Jul 6, 2017 at 19:04

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So, you mean that there exist problems which have brute force runtime as lower runtime bound? $\endgroup$
    – rus9384
    Commented Jul 7, 2017 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
    Commented Jul 7, 2017 at 9:14
  • $\begingroup$ Yeah, but in terms of functional problems it's be OK. $\endgroup$
    – rus9384
    Commented Jul 7, 2017 at 10:32

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.