$L_2$ = {a,k | is a 3DNF (disjunctive normal form) and exist z such that safifies exactly k clauses in a} Validity of reduction $VC \leq_p L_2$

I have the following question :

$ L_2$ = {$ a,k$ | $ a$ is a 3DNF (disjunctive normal form) and exist $ z$ such that satisfies exactly $ k$ clauses in $ a$ }

I know that $ L_2 \in NPC$ .

Show that $ L_2 \in NP$ is relatively easy, I’ll skip that part.

I try to show that $ L_2 \in NPC$ using a reduction from $ VC \leq_p L_2$ (VC is vertex cover which we know in its $ NPC$ )

I defined the following function $ f$ :

$ $ f(G,k)=(a,k)$ $

I thought of something like that for each node $ i$ in $ G$ will define a literal $ x_i$ , and make it in $ 3DNF$ format, $ a=\bigvee(x_i \wedge x_i \wedge x_i)$ where $ 1 \leq i \leq n$ where $ n$ is the number of nodes in $ G$ . We can define that following $ z$ such that $ z$ safifies exactly $ k$ clauses, just give $ ‘1’$ literal $ x_i$ such that the node $ i$ is in the VC, and $ ‘0’$ otherwise, so such $ z$ exists.

So easy to see that $ (G,k) \in VC \implies (a,k) \in L_2$ since we showed explicitly such $ z$ that safifies exactly $ k$ clauses.

But I’m not sure the other side holds $ (G,k) \not\in VC \implies (a,k)\not\in L_2$ we given a graph that doesn’t have VC in size $ k$ but I think due to my building of a ($ a=\bigvee(x_i \wedge x_i \wedge x_i)$ ) we can find $ z$ that safifies exactly $ k$ clauses (actually we can find $ z$ that safifies $ x$ clauses where $ 1 \leq x \leq n$ where $ n$ is number of nodes in G.

So my reduction doesn’t hold?


Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle

The following is an excerpt from a material on NP-Theory:
"Let G be an undirected graph and let s and t be vertices in G. A Hamiltonian path in G is a path from s to t using edges of G, on which each vertex of G appears once and only once. By HAM-PATH we denote the problem of determining, given G, s and t, whether G contains a Hamiltonian path from s to t. I now explain a reduction HAM-PATH < HAM-CYCLE. Let G, s, t constitute an input for HAM-PATH. We want to convert it to an input G′ (an undirected graph) for HAM-CYCLE. We add a new vertex u to the vertex set of G in order to obtain the vertex set for G′. The edges of G′ are all the edges of G plus two extra edges (u, s) and (t, u). I leave it to the reader to visualize that G′ contains a Hamiltonian cycle if and only if G contains a Hamiltonian path from s to t."

I am confused as to why do we need to add a vertex u to create G′. Why can’t we simply connect s and t and then check for a Hamiltonian Cycle. If it exists, then a path would also exist(as path is a sub-graph of cycle in an undirected graph) and we would be done. What am I missing? I am specially asking this for undirected graphs. I am clear about directed graphs that existence of cycle having s and t does not guarantee Hamiltonian path.
Illustrations or counter examples are welcome!

The definition of a graph’s transitive reduction

I want to determine the transitive reduction of this graph:


as of now, I only found the first step of doing this: represent the transitive closure of the graph as an adjacency relation, so this is what I did:

 (a,b)  (a,c)  (a,d)  (a,e)  (b,d)  (c,d)  (c,e)  (d,e) 

I’m not sure that this is the correct transitive closure of the graph, and I don’t know how to move forward in determining its transitive reduction.

A reduction from $HP$ to $\{(\langle M \rangle, \langle k \rangle) : \text{M visits in at list $k$ states for any input}\}$

I tried to define the next reduction from $ HP$ to $ \{(\langle M \rangle, \langle k \rangle) : \text{M visits in at list $ k$ states for any input}\}$ .

Given a couple $ (\langle M\rangle , \langle x\rangle)$ we define $ M_x$ such that for any input $ y$ , $ M_x$ simulates $ M$ on the input $ x$ . We denote $ Q_M +c$ the number of states needed for the simulation of $ M$ on $ x$ , and define more special states for $ M_x$ $ q_1′,q_2′,…,q_{Q_M + c+ 1}’$ when $ q’_{Q_M +c+1}$ is defined as the only final state of $ M_x$ . Now, in case $ M_x$ simulation of $ M$ on $ x$ halts (i.e $ M$ reach one of its finite state) $ M_x$ move to $ q_1’$ and then continue to walk through all the special states till it reaches $ q_{Q_M + c + 1}$ .

We define the reduction $ (\langle M \rangle , \langle x \rangle) \longrightarrow (\langle M_x \rangle , \langle Q_M +c+1 \rangle)$

In case $ ((\langle M \rangle , \langle x \rangle) \in HP$ then for any input $ y$ , $ M_x$ walks through all the special states and thus visits in at least $ Q_m + c+ 1$ steps. Otherwise, $ M$ doesn’t stop on $ x$ so $ M_x$ doesn’t visit any special state, thus visits at most $ Q_M +c$ states (the states needed for the simulation).

It is ok? If you have other ideas or suggestions please let me know.

reduction of independence problem and cluster problem

independent problem is: there is a simple and undirected graph, we are looking for the maximum vertex in which there is no edge between any two of them.

cluster problem is: there is a simple and undirected graph, we are looking for the maximum number of the vertex in which there are proximity every two vertexes ( there is an edge between any two vertexes)

how can I reduct independent problem to cluster problem and vise versa?

Damage reduction and damage resistance: how to calculate?

Assume a character has both damage reduction and damage resistance vs an incoming attack.

One example of damage reduction is the Heavy Armor Master feat:

While you are wearing heavy armor, bludgeoning, piercing, and slashing damage that you take from non magical weapons is reduced by 3.

One example of damage resistance is the blade ward cantrip:

You extend your hand and trace a sigil of warding in the air. Until the end of your next turn, you have resistance against bludgeoning, piercing, and slashing damage dealt by weapon attacks.

Let’s assume a character with both effects above is hit by a nonmagical weapon attack dealing slashing damage. The attack deals 10 damage. What happens:

  1. Damage reduction applies reducing damage to 7, then damage resistance (rounds down). Character takes 3 damage.
  2. Damage resistance applies, halving to 5, then damage reduction takes it to 2 damage.

Disagreement with professor over NP reduction problem

I’m a slight disagreement with my professor over whether or not a certain reduction is possible. He asked us to reduce the problem of 3-Coloring to the problem of 3-Clique. The problem is that I’m fairly confident that 3-Coloring is NP-Complete, while 3-Clique is P. Correct me if I’m wrong (which is very likely), but for any k-clique where the k is fixed, is $ V^k$ , meaning the 3-clique is $ V^3$ , right? I asked my professor about this and his response was:

“3-clique is definitely not in P. You (apparently) have to examine all thrices of vertices to settle the matter.”

And I still don’t understand how this is not a $ V^3$ operation.

If I figured out a way to reduce 3-coloring to 3-clique wouldn’t I be millionaire?

How does Max-HP reduction affect wild-shaped/polymorphed creatures?

Certain creatures have abilities which can reduce a character’s maximum HP, and usually if it gets reduced to 0 the character dies outright.

Suppose a HP30 PC is wild-shaped/polymorphed to a creature with 50HP, they get into a fight with a Wraith and take a few hits dealing a total of 30HP. If they failed the con saves, that PC’s max-HP is reduced by 30, but it’s still at 20.

An interesting, perilous situation.

Do they die instantly? Would feel a bit unfair since they’re standing there with a bunch of HP. Is the damage just shrugged off like normal damage upon return? The Druid’s wild-shape section is quiet on status conditions, though it’s pretty blatant about HP:

When you transform, you assume the beast’s hit points and Hit Dice. When you revert to your normal form, you return to the number of hit points you had before you transformed.

That sounds like a free pass, but it would reduce the danger of these fights considerably. I’ve been assuming the PC becomes a sort of ‘dead man walking’ where if they revert the HP reduction will carry and they’ll die instantly. But I’m not sure.

If that’s the case, they’ve got a ‘Crank’ like situation where the PC has less than an hour (before the wild-shape/polymorph wears off) to find a Heal or Remove Curse.

Does reduction of maximum hit points stick to the form it is applied to?

Following up on How does Max-HP reduction affect wild-shaped/polymorphed creatures?, which states:

Damage taken in animal form doesn’t affect your original form’s HP unless you’re dropped to 0 HP in animal form and there’s excess damage. Nowhere is it suggested that max-HP reduction would work any differently. Because Wild Shape/Polymorph gives you a new pool of HP, only that pool is affected by the reduction.


A druid gets seduced by a succubus. They kiss while the druid is in bear form – this is not hypothetical as yesterday exactly this had happened. The druid gets lowered Maximum Hit Points because of this forced romance. So according to the linked Q&A, the reduction would only apply to the bear form.


If the druid reverts back to normal, the HP reduction is not active anymore. What if the druid wild shapes another time, back into a bear: does it get a fresh “pool of HP”, or does the Reduced Max HP stay with its bear form until it gets “cured”?

In other words: are shapeshifters actually really resilient against abilities that reduce maximum hit points?


In case it helps to clarify, let’s use these numbers:

  1. Druid: 45 HP
  2. Wild Shapes into Brown Bear: 34 HP, but reduced to 10 Maximum HP (after two kisses).
  3. Druid reverts back to normal: 45 HP
  4. Wild Shapes back into Brown Bear: 34 HP, or still at 10 HP?