# 计算机代写|计算复杂度理论代写Computational complexity theory代考|CATS2013

## 计算机代写|计算复杂度理论代写Computational complexity theory代考|1-IN-3 SAT

An unfortunate feature of 3SAT is that each satisfied clause can have any of 1,2 , or 3 true literals. This turns out to be awkward when we try to reduce to problems that involve exact totals. Fortunately, we can show that 3SAT reduces to its more restrictive cousin 1-OF-3 SAT, defined as the set of all 3CNF formulas that have a satisfying assignment that makes exactly one literal in each clause true.

We do this by converting our original 3CNF formula one clause at a time. This involves adding a few extra variables specific to the representation of that clause.

To show how this works, let’s start with $x_1 \vee x_2 \vee x_3$. We’ll replace this clause with a new clause $y_1 \vee y_2 \vee y_3$, where $y_i \Rightarrow x_i$ but not necessarily conversely. These $y_i$ variables are new, and we use a separate trio for each original clause. This allows us to pick just one of the true $x_i$ literals to appear in the $y_1 \vee y_2 \vee y_3$ clause if there is more than one. To enforce that $y_i$ can be true only if $x_i$ is also true, we add three new 1-in-3 clauses, with three new variables: $\neg x_1 \vee y_1 \vee z_1, \neg x_2 \vee y_2 \vee z_2$, and $\neg x_3 \vee y_3 \vee z_3$. If any $x_i$ is false, this makes $\neg x_i$ in the corresponding clause true, so $y_i$ must also be false: so we can only satisfy $y_1 \vee y_2 \vee y_3$ if we satisfy $x_1 \vee x_2 \vee x_3$. But if $x_i$ is true, we have a choice between making $y_i$ true or $z_i$ true. The $z_i$ variables (which appear nowhere else) act as a sink for excess truth that would otherwise violate the 1-in-3 property.

Since this works for every clause, the output formula is in 1-IN-3 SAT if and only if the input formula is in 3SAT. Since the reduction is obviously polynomial (it’s linear), this gives 3SAT $\leq_P$ 1-IN-3 SAT, making 1-IN-3 SAT NP-hard. But it’s also in NP, since in polynomial time we can easily guess the satisfying assignment and check that it has the 1-in-3 property. So 1-IN-3 SAT is NP-complete.

## 计算机代写|计算复杂度理论代写Computational complexity theory代考|Reductions through INDEPENDENT SET

INDEPENDENT SET is the problem of determining, given $G$ and $k$, whether $G$ contains an independent set of size $k$. An independent set is a subset $S$ of the vertices of $G$ such that no edge has both endpoints in the subset. We can show INDEPENDENT SET is NP-hard by reducing from 3SAT.

The idea is that any clique in $G$ can’t contain more than one element of $S$, so if we can partition $G$ into $k$ non-overlapping cliques, then each of these cliques must contain exactly one element of $S$. We use this constraint to encode variable settings as 2-cliques (also known as edges): for each $x_i$, create nodes representing $x_i$ and $\neg x_i$, and put an edge between them. We’ll call these the master copies of $x_i$ and $\neg x_i$.

We can then represent a clause $C_j=x \vee y \vee z$ as a 3-clique of copies of $x, y$, and $z$ (which may be negated variables). Here the member of $S$ in the representation of $C_j$ indicates which of the three literals we are using to demonstrate that $C_j$ is satisfiable. These are per-clause copies; we make a separate vertex to represent $x$ in each clause it appears in.

The remaining step for the graph is to make sure that whatever literal we chose to satisfy in $C_j$ is in fact assigned a true value in the 2-clique representing the corresponding $x_i$ or $\neg x_i$. We do this by adding an extra edge from the per-clause copy in $C_j$ to the master copy of the opposite value in the 2-clique; for example, if we have a copy of $x_i$ in $C_j$, we link this copy to the node representing $\neg x_i$, and if we have a copy of $\neg x_i$ in $C_j$, we link this copy to the node representing $x_i \cdot{ }^4$

Finally, we set $k=n+m$, where $n$ is the number of variables (and thus the number of master-copy 2-cliques) and $m$ is the number of clauses (and thus the number of clause 3 -cliques). This enforces the one-element-per-clique requirement.

It is easy to see that this reduction can be done in polynomial (probably even linear) time. It remains to show that it maps satisfiable formulas to graphs with independent sets of size $k$ and vice versa.

# 计算复杂度理论代考

## 计算机代写|计算复杂度理论代写Computational complexity theory代考|1-IN-3 SAT

3SAT 的一个不幸特征是每个满足的子句可以有 1,2 或 3 个真实文字中的任何一个。当我们试图简化为涉及精确总数的问题时，这会变得很尴尬。幸运的是，我们可以证明 3SAT 减少到其更具限制性的表亲 1-OF-3 SAT，定义为所有 3CNF 公式的集合，这些公式具有令人满意的分配，使每个子句中的一个文字为真。

## 计算机代写|计算复杂度理论代写Computational complexity theory代考|Reductions through INDEPENDENT SET

INDEPENDENT SET 是确定的问题，给定G和k， 无论G包含一组独立的大小k. 独立集是子集小号的顶点G这样子集中没有边具有两个端点。我们可以通过从 3SAT 减少来证明 INDEPENDENT SET 是 NP-hard。

myassignments-help数学代考价格说明

1、客户需提供物理代考的网址，相关账户，以及课程名称，Textbook等相关资料~客服会根据作业数量和持续时间给您定价~使收费透明，让您清楚的知道您的钱花在什么地方。

2、数学代写一般每篇报价约为600—1000rmb，费用根据持续时间、周作业量、成绩要求有所浮动(持续时间越长约便宜、周作业量越多约贵、成绩要求越高越贵)，报价后价格觉得合适，可以先付一周的款，我们帮你试做，满意后再继续，遇到Fail全额退款。

3、myassignments-help公司所有MATH作业代写服务支持付半款，全款，周付款，周付款一方面方便大家查阅自己的分数，一方面也方便大家资金周转，注意:每周固定周一时先预付下周的定金，不付定金不予继续做。物理代写一次性付清打9.5折。

Math作业代写、数学代写常见问题

myassignments-help擅长领域包含但不是全部: