您好,欢迎来到二三四教育网。
搜索
您的当前位置:首页algorithms-ch8: P, NP, NP-Hard a

algorithms-ch8: P, NP, NP-Hard a

来源:二三四教育网

概念

  • Search Problem(eg:SAT)
    search problem can be verified in polynomial time is NP (all search problem is NP); search problem can be solved in polynomial time is P

  • Search problem is NP-complete: if all other search problems reduce to it.

  • Decision Problem
    A decision problem is a problem whose answer is YES or NO

  • P (Polynomial time)
    The class P is the set of all decision problems that can be solved in polynomial time in the size of their encoding (ie. polynomial number of operations)

  • NP (Nondeterministic Polynomial time)
    The set of all decision problem such that if the answer is YES then there is a certificate of validity that can be checked in polynomial time in the size of their input (a yes answer for a decision problem can be verified in polynomial time)

  • co-NP
    The set of all decision problem such that if the answer is NO then there is a certificate of validity that can be checked in polynomial time in the size of their input (a no answer for a decision problem can be verified in polynomial time)

定理各种

  • Theorem1: P is a subset of NP. Also, P is a subset of co-NP
    (But it is not known if P=NP or if NP=co-NP)

  • Polynomial time reducibility
    A decision problem P1 is polynomially reducible to a decision problem P2 (if given any instance of P1 we can convert it to an instance of P2 in polynomial time), so that P1 is true if and only if P2 is true.
    We write P1=<P2, which means that P1 is at least as hard as P2.

  • NP-Completeness(CNF-SAT, cli)
    A decision problem P is NP-Complete if two conditions are satisfies:(1) It is NP; (2) Every other problem P' in NP is polynomially reducible to P.

Copyright © 2019- how234.cn 版权所有 赣ICP备2023008801号-2

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务