9

I am given a Boolean expression of arbitrary depth, like (A or (B and (C or (~D and E) or F) or (G and H))). There can be any number of terms at each level.

I want to limit the depth of the expression (the maximum depth of nested parentheses + 1) to some constant like 4. If the depth exceeds that bound, then I want to generate an equivalent expression with depth that does not exceed the bound.

I know that I can convert to CNF or DNF, which would limit the depth to 2, but the size of the expression can blow up exponentially.

How can I take advantage of more available levels to limit the size of the resulting expression as much as possible?

Improve this question
10
  • "but the size of the expression can blow up exponentially" - that'll still happen no matter what limit you choose. Commented Nov 18, 2024 at 22:44
  • How exactly do you measure the size that you want to minimise? Commented Nov 18, 2024 at 22:45
  • @Bergi The size I want to minimize would be the total number of terms. I expect that it may still blow up exponentially, but maybe I can reduce the base? Commented Nov 18, 2024 at 23:33
  • 1
    @btilly Good luck :D Commented Nov 19, 2024 at 10:44
  • 2
    @DevQt The origin of this problem is a bit esoteric. It arises because I have to return a Boolean expression from a GraphQL server. There are a few different ways to do it, but the "friendliest" way, returning it as a GraphQL object, requires establishing a maximum depth, because the GraphQL query language does not actually have the ability to request a structure of unbounded depth. It's just a limitation of the language. So the real-life possibility of expressions becoming large when depth is limited needs to be traded off against other ways of returning the object. Commented Nov 24, 2024 at 2:35
Related questions
3610
How can I convert a string to boolean in JavaScript?
2088
What is the optimal algorithm for the game 2048?
1691
What is the best algorithm for overriding GetHashCode?
Load 7 more related questions Show fewer related questions

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.