Using a rash decision to move gameplay forward

I DM’d my first game recently, I’m pretty happy with how it turned out, and most of the group were pretty lax about the quality of it all, so it all went fairly smoothly.

However, there is one thing that stuck in my head and I want to try and come up with a way to deal with the group arguing what should be done next.

In my game, the group couldn’t decide whether or not to take door A or tunnel B, and it was all getting a bit out of hand, so I decided as the DM, to take the first thing someone said as an action. So when someone said “Why don’t we just kick down the door and charge in?” I said “Ok, so the Paladin is charging in!”

The group discussion ended fairly quickly but not everyone was happy about the outcome.

What I’m asking is if there is a better way to move the game forward when players are constantly bickering about what they should do.

New player decision paralysis

I’m introducing a new player to RPGs. She struggles to put herself in the mindset of her character and make the decisions the character would make, which is the essence of role-playing.

She can get by by going along with others’ prompting, but if she alone must decide what action to take, she stops and thinks until I get impatient and any sense of game flow is lost. I don’t expect all decisions to be made instantly, but I expect routine “what do you do next?” decisions to be made in under a minute and get faster with experience.

I tried prompting/pressuring for decisions, directly and by using game characters as a proxy. The feedback after the session was that she found it stressful and unhelpful, not motivational.

I haven’t been able to break down my own in-character decision-making process to pass on to her. I’m practiced enough to just do it somehow.

I strongly favour rules-light games that emphasise game-world focus rather than abstract mechanical focus, so all mechanics must really carry their weight, but this is such a burden that I will consider including mechanics that will help.

In summary, please share something to help with fast in-character decision-making:

  • A breakdown of the process that a new player could follow.
  • Game mechanics (from any game) which could help.
  • Advice in how to deal with this; for me or for her, I don’t mind.

(This is not a duplicate of How do I get my players to be more decisive and take the initiative? because that is about structured vs unstructured scenarios, whereas my question is about single decisions within any scene.)

What to say if a decision problem is not NP?

Let $ O$ be an optimisation problem and $ P$ its decision variant. I know that $ O$ is said to be NP-hard if $ P$ is $ NP-$ complete. However, what to say about $ O$ when the decision problem $ P$ is no more in the class $ NP$ , and thus it’s no more $ NP-$ complete(the algorithm of deciding is pseudo-polynomial and there is no better alternatives)?

Why decision tree method for lower bound on finding a minimum doesn’t work

(Motivated by this question. Also I suspect that my question is a bit too broad)

We know $ \Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison and each leaf is a permutation. Since there are $ n!$ leaves, the minimum tree height is $ \Omega(\log (n!)) = \Omega (n \log n)$ .

However, it doesn’t work for the following problem: find a minimum in the array. For this problem, the results (the leaves) are just indices of the minimum element. There are $ n$ of them, and therefore the reasoning above gives $ \Omega(\log n)$ lower bound, which is obviously an understatement.

My question: why does this method works for sorting and doesn’t work for minimum? Is there some greater intuition or simply "it just happens" and we were "lucky" that sorting has so many possible answers?

I guess the lower bound from decision tree makes perfect sense: we do can ask yes/no questions so that we need $ O(\log n)$ answers: namely, we can use binary search for the desired index. My question still remains.

Grammar and Enumerator for Decision and Halting Problem

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since decision problem and halting problem are recursively enumerable, I was wondering what kind of grammar and enumerator could this be.

Ok since there exists a sequence of M_i I would start with M_1 and find all words for this TM and give them out. So if I have any TM is there a possibility to give all words out which are accepted by this TM? I probably would have to give all w_i to it and compute the first i words for i steps, then i+1 words for i+1 steps and so on. Or maybe something like DFS on all configurations. This really sounds like that only for one TM this could go on forever. So I would need to start the second TM for the same period of time after a while… Seems as if something similiar could work for Halting Problem. Do you have any more refined thoughts on this one?

But the Problem with the Grammar seems to be more challenging. How could I possibly come up with a Grammar for these problems? You would have to generate code(M_i) in such a way that its always in the language. So you would have to simulate the TM through grammmar on different words. It somewhat comes down to the question whether a TM accepts anything or holds on any entry. Or is it more "okay we proofed, so there must be some kind of grammar even though I canĀ“t comeup with an idea for it".

Greets,

Felix

If a decision problem’s solution is exponentially large, then is it impossible for it to be in $NP$?

Decision Problem: Is $ 2^k$ + $ M$ a prime?

The inputs for both $ K$ and $ M$ are integers only. The solution is the sum of $ 2^k$ +$ M$ . (Use AKS to decide prime)

The powers of 2 have approximately $ 2^n$ digits. Consider $ 2^k$ where $ K$ = 100000. Compare the amount of digits in $ K$ to the amount of digits in it’s solution!

Question

Could the solution be verified in polynomial time even though the solution is exponentially large?

If no, can I say it is not in $ NP$ ?

Is the complement of this decision problem in $P$?

Are there any two primes that are NOT a factor of $ M$ that multiply up to $ M$ ?

Fact: Any two primes that multiply up to $ M$ . Must be factors of $ M$ !

Thus because of the fact above an $ O(1)$ algorithm exists. It always outputs $ NO$

Complement

Are there any two primes that are a factor of $ M$ that multiply up to $ M$ ?

Fact: A complement of a decision problem does not always require to always return $ YES$ or $ NO$ . It can be either one!

(eg. $ M$ = 6 and two primes that multiply up to $ M$ are $ 3$ ,$ 2$ .)

Well, this I find interesting this is deciding $ Semi-Primes$ .

Question

Shouldn’t $ Semi-Primes$ be in $ P$ , because what was shown above?

If a decision problem is in $P$, must finding the solution be possible in polynomial-time?

Function Problem that finds the solution

  • Given integer for $ N$ .

  • Find $ 2$ integers distinct from $ N$ . (But, less than $ N$ )

  • That have a product equal to $ N$ .

This means we must exclude integers $ 1$ and $ N$ .

An algorithm that is pseudo-polynomial

N = 10  numbers = []  for a in range(2, N):     numbers.append(a)   for j in range(length(numbers)):   if N/(numbers[j]) in numbers:    OUTPUT N/(numbers[j]) X numbers[j]    break 

Output

Soltuion Verified: 5 x 2 = N and N=10 

The algorithm that solves the Decision Problem

if AKS-primality(N) == False:   OUTPUT YES 

Question

Since the decision problem is in $ P$ must finding a solution also be solvable in polynomial-time?