翻訳と辞書 Words near each other ・ Maxcy Gregg ・ Maxdalury ・ Maxdata ・ Maxdata Software ・ MaxDB ・ MaxDDBS ・ MaxDiff ・ Maxdo Centre ・ Maxdorf ・ Maxdorf (Verbandsgemeinde) ・ MaxDrive ・ Maxed Out ・ Maxeda ・ Maxeen ・ Maxeen (album) ・ MAXEkSAT ・ Maxelende Ganade ・ Maxen (disambiguation) ・ Maxence ・ Maxence Bibié ・ Maxence Caron ・ Maxence Cyrin ・ Maxence Flachez ・ Maxence Larrieu ・ Maxence Layet ・ Maxence Mailfort ・ Maxence Medjelled ・ Maxence Muzaton ・ Maxence Parrot ・ Maxence Perrin Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク MAXEkSAT ： ウィキペディア英語版 MAXEkSAT MAXEkSAT is a problem in computational complexity theory that is a maximization version of the Boolean satisfiability problem 3SAT. In MAXEkSAT, each clause has exactly ''k'' literals, each with distinct variables, and is in conjunctive normal form. These formulas are called k-CNF formulas. The problem is to determine the maximum number of clauses that can be satisfied by a truth assignment to the variables in the clauses. We say that an algorithm ''A'' provides an ''α''-approximation to MAXEkSAT if, for some fixed positive ''α'' less than or equal to 1, and every kCNF formula ''φ'', ''A'' can find a truth assignment to the variables of ''φ'' that will satisfy at least an ''α''-fraction of the maximum number of satisfiable clauses of ''φ''. Because the NP-hard ''k''-SAT problem (for ''k'' ≥ 3) is equivalent to determining if the corresponding MAXEkSAT instance has a value equal to the number of clauses, MAXEkSAT must also be NP-hard, meaning that there is no polynomial time algorithm unless P=NP. A natural next question, then, is that of finding approximate solutions: what's the largest real number ''α < 1'' such that some explicit P (complexity) algorithm always finds a solution of size ''α·OPT'', where ''OPT'' is the (potentially hard to find) maximizing assignment. ==Approximation Algorithm== There is a simple randomized polynomial-time algorithm that provides a $\backslash textstyle(1-\backslash frac)$-approximation to MAXEkSAT: independently set each variable to true with probability , otherwise set it to false. Any given clause ''c'' is unsatisfied only if all of its ''k'' constituent literals evaluates to false. Because each literal within a clause has a chance of evaluating to true independently of any of the truth value of any of the other literals, the probability that they are all false is $\backslash textstyle(\backslash frac)^k\; =\; \backslash frac$. Thus, the probability that ''c'' is indeed satisfied is $\backslash textstyle\; 1-\backslash frac$, so the indicator variable $\backslash textstyle\; 1\_c$ (that is 1 if ''c'' is true and 0 otherwise) has expectation $\backslash textstyle\; 1-\backslash frac$. The sum of all of the indicator variables over all $\backslash textstyle|C|$ clauses is $(\backslash textstyle\; 1-\backslash frac)|C|$, so by linearity of expectation we satisfy a $\backslash textstyle\; (1-\backslash frac)$ fraction of the clauses in expectation. Because the optimal solution can't satisfy more than all $\backslash textstyle\; |C|$ of the clauses, we have that $\backslash textstyle\; ALG\; =\; (1-\backslash frac)\backslash cdot\; |C|\; >\; (1-\backslash frac)\backslash cdot\; OPT$, so the algorithm finds a $\backslash textstyle\; \backslash geq\; (1-\backslash frac)$ approximation to the true optimal solution in expectation. Despite its high expectation, this algorithm may occasionally stumble upon solutions of value lower than the expectation we computed above. However, over a large number of trials, the average fraction of satisfied clauses will tend towards $\backslash textstyle\; (1-\backslash frac)$. This implies two things: # There must exist an assignment satisfying at least a $\backslash textstyle\; (1-\backslash frac)$ fraction of the clauses. If there weren't, we could never attain a value this large on average over a large number of trials. # If we run the algorithm a large number of times, at least half of the trials (in expectation) will satisfy some $\backslash textstyle\; (1-\backslash frac)$ fraction of the clauses. This is because any smaller fraction would bring down the average enough that the algorithm must occasionally satisfy more than 100% of the clauses to get back to its expectation of $\backslash textstyle\; (1-\backslash frac)$, which cannot happen. Extending this using Markov's inequality, at least some $\backslash textstyle\; (\backslash frac)$-fraction of the trials (in expectation) will satisfy at least an $\backslash textstyle\; (1-\backslash frac-\backslash epsilon)$-fraction of the clauses. Therefore, for any positive $\backslash textstyle\; \backslash epsilon$, it takes only a polynomial number of random trials until we expect to find an assignment satisfying at least an $\backslash textstyle\; (1-\backslash frac-\backslash epsilon)$ fraction of the clauses. A more robust analysis (such as that in 〔(Max-SAT )〕) shows that we will, in fact, satisfy at least a $\backslash textstyle\; (1-\backslash frac)$-fraction of the clauses a constant fraction of the time (depending only on ''k''), with no loss of $\backslash textstyle\; \backslash epsilon$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「MAXEkSAT」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.