题目内容

If $NP\neq co-NP$, then $P \neq NP$.

查看答案

搜索结果不匹配？点我反馈

更多问题

Decide whether you think the following statement is true or false.$G\ $ is a flow network with a maximum flow which has a value of $v(f)$. Consider the flow network $G'$ obtained by adding $1$ to the capacity of every edge. The value of the maximum flow in $G'$ is $v(f) + 1\ $.

A. 正确
B. 错误

We have a function $f(x)=2x^2-9x+3$. We want to get the minimize value of $f$ and define neighbors of $x$ are $x-1$ and $x+1$. We start at $x = 0$. The algorithm finds a local optimum at $x$ =_____.

A. 1
B. 2
C. 3
D. 4

Decide whether you think the following statement is true or false. Let $G$ be an arbitrary flow network, with a source $s$, a sink $t$, and a positive integer capacity $c_e$ on every edge $e\ $. Let $(A, B) $ be a mimimum $s-t$ cut with respect to these capacities $\{c_e: e\in E\}$. Now suppose we add $1$ to every capacity, then $(A, B) $ is still a minimum $s-t$ cut with respect to these new capacities $\{1+c_e: e\in E\}$.

A. 正确
B. 错误

Coin is heads with probability 1/3 and tails with probability 2/3. The expectation of independent flips until first heads is _____.

A. 1
B. 2
C. 3
D. O($\log n$)