## Does reducing the Purple Worm’s HP to 184 really reduce its challenge rating to 13?

On page 113 of Princes of the Apocalypse the text reads in part:

As the tremor ends, a young purple worm with 184 hit points (challenge rating 13) burrows…

No other changes to the Purple Worm’s stats are given and the monster does not appear in the Monsters section at the end of the book. This monster also shows up on DnD Beyond’s encounter builder as a CR 13 monster as "Young Purple Worm", in contrast to the CR 15 "Purple Worm".

Is taking away 63 hit points with no other changes to this monster enough to drop it two challenge ratings? I’d like to challenge, but not kill, my party.

## Will reducing the cost of Holy Water or improving its effectiveness break things

My L3 LMoP group are planning on picking up some holy water to help with zombies as they’ve heard to tales of undead (old owl well, and thunder tree), but I think they’re going to be very disappointed to find its 25Gp, but is single use, costs an action, affects a single target, and only does the same damage as a greatsword swing.

Essentially, it seems to be only as good as a single decent fighter attack, but uses an action and costs 25Gp. Given that an average L3 PC might expect to do say ~D6 +3 damage with a typical attack, this means they’re getting about 3 extra damage, once, for 25Gp, which seems absurd. Plus it only works on certain foes.

Am I missing something?!

I’d like to make this work for them, so I’m considering some changes to the rules for Holy Water:

1. Reduce the cost – maybe as low as 5Gp, given that they have a paladin who is visiting a temple to make his oath (this allows me to keep the price higher on other occasions if they did find a way to abuse it)
2. Make it more effective – maybe an AoE effect?

Will this break the game, or be something they can heavily abuse later?

## Is there an algorithm for reducing CNFs further

I have a boolean formula in conjunctive normal form (CNF): $$(a\vee b \vee c) \wedge (a \vee b \vee \neg c) \wedge (x \vee y)$$

I know that this can be simplified to: $$(a\vee b)\wedge (x \vee y)$$.

a) Is there an algorithm to decide if a CNF is already in the reduced form or not?

b) Is there an algorithm that can do this reduction in an manner more efficient than comparing each pair of clauses to see if any pairing can be reduced? I wish to automate this reducing for any CNF and am looking for any algorithms that I can borrow/implement.

## Does reducing a character’s max HP with a spell also reduce the “negative HP” threshold needed to cause instant death?

Here’s my situation: In a fight with a group of vampire thralls, the party’s wizard got caught in a corner and was being savaged by vampire bites, his max HP dropping from 24 to 11. They fended off the vampires, but the wizard was at 3hp (He refused to be healed by the cleric due to his character’s hatred of religion and gods). He activated a trap collapsing the temple, and ended up getting hit by a falling chunk of stone ceiling, taking 15 damage (the rock rolled better than any of the vampires).

Now, the wizard is reduced to 0 hp, with 12 damage left over. The cleric’s player says that exceeds the wizard’s current max hp of 11, causing insta-death. The wizard’s player argues that the death threshold for negative HP isn’t affected by max-hp-reducing spells, claiming that would make those kinds of spells more powerful than intended.

I have stories planned in either case, but I’d rather be certain that I’m following the rules.

Is the threshold for instant death based on current max hp or normal max hp?

## Reducing Dominant Set Problem to SAT

I am trying to solve a problem and I am really struggling, I would appreciate any help.

Given a graph $$G$$ and an integer $$k$$ , recognize whether $$G$$ contains dominating set $$X$$ with no more than $$k$$ vertices. And that is by finding a propositional formula $$\phi_{G,k}$$ that is only satisfiable if and only if there exists a dominating set with no more than k vertices, so basically reducing it to SAT-Problem.

What I have so far is this boolean formula:

$$\phi=\bigwedge\limits_{i\in V} \bigvee\limits_{j\in V:(i,j)\in E} x_i \vee x_j$$

So basically defining a variable $$x_i$$ that is set to true when when vertix $$v_i$$ is in the dominating Set $$X$$, so all the formula says that it is satisfiable when for each node in $$G$$ it is true that either the vertex itself is in $$X$$ or one of the adjacent vertices is. Which is basically a Weighted Satisfiability Problem so its satisfiable with at most $$k$$ variables set to true.

My issue is now that I couldn’t come up with a boolean formula $$\phi_{G,k}$$ that not only uses Graph $$G$$ as input but also integer $$k$$. So my question is now how can I modify this formula so it features $$k$$ , or possibly come up with a new one if it cannot be modified?

## How does resistance/vulnerability/immunity interact with carryover damage after reducing a Polymorphed (or Wild Shaped) form to 0 HP?

A caster casts polymorph on another creature. Let’s say the polymorphed creature has 10 HP in its new form, but takes 30 piercing damage and its current form is reduced to 0 HP. This causes it to revert back to its original form, with 20 more piercing damage that would carry over. However, its original form is resistant to piercing damage.

How much damage would the new form actually take? Would its original form’s resistance to the damage type apply to the carryover damage?

The same question can be extended to the original form having immunity or vulnerability, as the answer would ostensibly use the same logic.

The druid’s Wild Shape ability also works similarly to polymorph in this regard (if you reduce the new form to 0 HP, then any remaining damage carries over to its original form), so I suspect the answer would be similar for a similar question about Wild Shape.

## Reducing 3-coloring problem to trio representatives

A group of students is divided into trios – groups of 3 members. Each student can be assigned to more than more trio. We want to assign their representatives, by choosing exactly one member of each trio. Is such assignment possible?

My goal is to use polynomial-time reductions to transform 3-coloring of a graph into this problem. However, I’m stuck on the correct representation.

• If each vertex is a different student and edges represent being in the same trio, how do I separate trios?

• If each node represents a trio, what could be a sensible meaning of the edges?

I suspect that since a 4-clique has no adequate 3-coloring (which could also mean that 4 trios with the same three members have no possible representative assignment), the latter option could be more sensible, but I’m not sure on how to proceed with this reduction proof.

## The Partition Problem: Reducing to prove NP-Completeness

I am struggling with the below problem. Curious to hear any guidance.

The Partition Problem is the following:

$$\textbf{Instance:}$$ A (multi-)set of numbers $$S = \{a_1, a_2, \ldots , a_n \}$$.

$$\textbf{Question:}$$ Can $$S$$ be partitioned into two (multi-)sets $$A$$ and $$B$$ such that the sum of the numbers in $$A$$ is equal to the sum of the numbers in $$B$$?

Prove that the Partition Problem is NP-complete.

Things I could reduce from that I know of are 3-SAT, Vertex Cover, Subset Sum, Independent Set, and the clique problem. My assumption is that I should be reducing from the Subset Sum problem, but I struggle with that problem as well.

Anyone able to help shed some light on this? Also, any explanation in plain english (maybe with some notation) would be greatly appreciated as I’m struggling with the concepts here. Just mathematical notation alone might make it more difficult for me to understand at the moment.

## Reducing Vertex Cover to Half Vertex Cover

I need to reduce Vertex Cover to Half Vertex Cover using a Karp reduction:

Vertex Cover: Given a graph $$G = (V,E)$$ and an integer $$k$$, is there a subset of $$V$$ of size $$k$$ which intersects all edges?

Half Vertex Cover: Given a graph $$G = (V,E)$$ and an integer $$k$$, is there a subset of $$V$$ of size $$k$$ which intersects exactly half the edges?

I will be happy if you can tell me how to do that and why the reduction works (both directions of the proof).

## Reducing Kleene’s predecessor for Church numerals

I am trying to “reinvent” Kleene’s predecessor myself. The following code snippet should be self-explanatory. The idea is to make a 2-tuple and count up from zero, i.e. lambda f: lambda x: x, as described in this article:

#!/usr/bin/env python3  NULL = lambda x: x ZERO = lambda f: lambda x: x  TRUE = lambda T: lambda F: T(NULL) FALSE = lambda T: lambda F: F(NULL) IF_ELSE = lambda cond: lambda T: lambda F: cond(T)(F) IS_ZERO = lambda n: n(lambda _: FALSE)(TRUE)  ADD1 = lambda n: lambda f: lambda x: f(n(f)(x))  MakePair = lambda first: lambda second: lambda cond: IF_ELSE(cond)(lambda x: first)(lambda x: second) First = lambda pair: pair(TRUE) Second = lambda pair: pair(FALSE) Trans = lambda pair: lambda cond: IF_ELSE(cond)(lambda x: Second(pair))(lambda x: ADD1(Second(pair))) SUB1 = lambda n: First(n(Trans)(MakePair(ZERO)(ZERO)))  THREE = ADD1(ADD1(ADD1(ZERO))) FIVE = ADD1(ADD1(ADD1(ADD1(ADD1(ZERO)))))  if __name__ == '__main__':     print(SUB1(THREE)(lambda x: x + 1)(0))     print(SUB1(FIVE)(lambda x: x + 1)(0)) 

In the end, the linked article notes that

It is then straightforward but tedious to expand all of the short-hand expressions above, and reduce the resulting expression to normal form. This results in the standard magical encoding of predecessor.

I assume the normal form of Kleene’s predecessor looks like this:

pred = lambda n: lambda f: lambda x: n (lambda g: lambda h: h (g (f))) (lambda y: x) (lambda x: x) 

However, after applying a series of expansion and $$\beta$$-reduction, I ended up with this:

SUB1 = lambda n: n(lambda pair: lambda cond: cond(lambda x: pair(lambda T: lambda F: F(NULL)))(lambda x: lambda f: lambda x: f((pair(lambda T: lambda F: F(NULL)))(f)(x))))(lambda _: lambda f: lambda x: x)(lambda T: lambda F: T(lambda x: x)) 

Question:

How do I reduce my SUB1 function to pred? I don’t think we can go further with only $$\beta$$-reduction, and there must be some advanced reduction techniques unknown to me.

A step-by-step solution would be greatly appreciated. Note that this is not a homework problem though; I am doing the exercise just for fun.