# Tag Info

7

Any upwards-closed non-empty class $\mathfrak{L}$ of languages has the cardinality of the continuum, with very few limitations on what kind of reasonable reducibility we are looking at. The reason is if $A \in \mathfrak{L}$ and $B$ is an arbitrary language, then the language $A + B = \{0w \mid w \in A\} \cup \{1w \mid w \in B\}$ satisfies that $A \leq A + B$,...

7

You haven't explained what graph isomorphism means for you, so let me assume that you mean the language of all pairs of graphs $(G_1,G_2)$ which are isomorphic. Two graphs $G_1 = (V_1,E_1),G_2 = (V_2,E_2)$ are isomorphic if there exists a bijection $f\colon V_1 \to V_2$ such that $(x,y) \in E_1$ iff $(f(x),f(y)) \in E_2$. You take it from here.

4

If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case. If, however, $P \neq NP$, then there are languages which are neither in NP nor NP-hard. For example, we can consider the language $\{1^n \mid \text{the } n\text{-th TM halts}\}$. As this ...

3

Let $S, k$ be a given instance of the subset sums problem. The goal is to build an equivalent instance of your problem (let us call it the pens arrangement problem). In the subsetsums problem, we are looking for a subset of the given set that sums up to $k$. So it is intuitive to set $G$ to $k$ and set the lengths of the pens to be the numbers in the given ...

2

Your question is very philosophical in nature because you are asking about what is considered by computation and it’s physical implementations. In short, there is a ongoing discussion on different accounts of concrete computation e.g. the simple mapping account, the semantic account, the syntactic account, the mechanistic account, the causal, the ...

2

Let us consider the following decision version of your first problem: Given a SAT instance, does its multilinear representation have a term of degree at most $d$? I claim that this is the case iff the SAT instance has a satisfying assignment with at most $d$ ones. Indeed, suppose first that $m$ is an inclusion-minimal term in the multilinear ...

2

Here is a reduction from the Hamiltonian path. Given a graph $G=(V,E)$. Add a vertex $v_0$ to the graph and connect it to all vertices in the graph. Set $t(v_0)=2$. Set $t(u) = 1$ for all $u \neq v_0$. Claim. The previous reduction is correct. Try to prove it formally as an exercise. Edit. Here is a brief proof of correctness. We have to prove that the ...

1

The set $S$ consists of $12$ numbers. Hence it has $2^{12} = 4096$ subsets. You can write a computer program that goes over all subsets, sums each of them, and determines whether the sum is $492$, in which case it prints the subset.

1

To prove a problem is NP-complete you have to prove it is in NP and that it is NP-hard. NP-hardness proof is usually however, a reduction from one NP-hard problem. To prove that the problem is NP, you can either describe a non-deterministic polynomial time algorithm for the problem (An NTM that decides the language of the yes-Instances in polynomial time), ...

1

The accepted answer is incorrect: assuming $P\not=NP$ there are lots of problems incomparable with $SAT$, hence neither $NP$ nor $NP$-hard. Here's an overkill generalization of this fact: Suppose $X\not\in P$. Then there is some $Y$ such that $Y$ is incomparable with $X$ under polynomial-time-Turing reducibility (hence a fortiori Karp reducibility). (So ...

Only top voted, non community-wiki answers of a minimum length are eligible