Is the max HP reduction from the Diseased Giant Rat permanent?

The variant Diseased Giant Rat (MM pg. 327) has a feature that when it hits with an attack and the target fails a saving throw, they contract a disease. The text says

Until the disease is cured the target can’t regain hit points except by magical means, and the target’s hit point maximum decreases by 3 (1d6) every 24 hours. […]

Is this reduction permanent or will the character regain their original maximum HP when cured of the disease?

My confusion stems from the fact that all information about the effect follows the "Until the disease is cured" statement, which could mean that the reduction only lasts until the target is cured. On the other hand one could argue that it is only further reductions that are mentioned and thus prevented by curing the target and the previous ones are separate effects that has already taken place.

Does damage reduction from Shadowfell Brand Tattoo stack with resistance?

Shadowfell Brand Tatoo, the new magic item from Tasha has this effect:

Shadowy Defense. When you take damage, you can use your reaction to become insubstantial for a moment, halving the damage you take. Then the reaction can’t be used again until the next sunset.

Does this reduction stack with reduction from having resistance?

$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?