Chuyển bộ gõ


Từ điển Máy Tính - Foldoc Dictionary
satisfiability problem



satisfiability problem

A problem used as an example in complexity theory. It can be stated thus:

 Given a Boolean expression E, decide if there is some  assignment to the variables in E such that E is true. 
A Boolean expression is composed of Boolean variables, (logical) negation (NOT), (logical) conjunction (AND) and parentheses for grouping. The satisfiability problem was the first problem to be proved to be NP-complete (by Cook).

["Introduction to Automata Theory, Languages, and Computation" by Hopcroft and Ullman, pub. Addison-Wesley].

Last updated: 1994-11-11




Giới thiệu VNDIC.net | Plugin từ diển cho Firefox | Từ điển cho Toolbar IE | Tra cứu nhanh cho IE | Vndic bookmarklet | Học từ vựng | Vndic trên web của bạn

© Copyright 2006-2024 VNDIC.NET & VDICT.CO all rights reserved.