2 added 6 characters in body
source | link

I have already defined here what is minimal 3CNF formula.

In the answer to the question, D.W. answered:

What you are thinking is wrong. A minimal, unsatisfiable formula can have more than 8 clauses.

In response to:

In a minimal k-cnf formula, there should be 2k different k literals clauses exactly, so in a minimal 3CNF formula, there should be 23=8 different 3 literals clauses exactly.

So my question is now, what is the largest possible minimal 3CNF formula or how many clauses there are in the largest possible minimal 3CNF formula, i.e. what is the maximum number of clauses in the largest minimal 3CNF formula as function of n, where n is the number of variables in the 3CNF formula.

Is it O(n)$O(n)$? Is it O(log(n))$O(log(n))$? Is it O(1)$O(1)$, but just larger than 8?

I have already defined here what is minimal 3CNF formula.

In the answer to the question, D.W. answered:

What you are thinking is wrong. A minimal, unsatisfiable formula can have more than 8 clauses.

In response to:

In a minimal k-cnf formula, there should be 2k different k literals clauses exactly, so in a minimal 3CNF formula, there should be 23=8 different 3 literals clauses exactly.

So my question is now, what is the largest possible minimal 3CNF formula or how many clauses there are in the largest possible minimal 3CNF formula, i.e. what is the maximum number of clauses in the largest minimal 3CNF formula as function of n, where n is the number of variables in the 3CNF formula.

Is it O(n)? Is it O(log(n))? Is it O(1), but just larger than 8?

I have already defined here what is minimal 3CNF formula.

In the answer to the question, D.W. answered:

What you are thinking is wrong. A minimal, unsatisfiable formula can have more than 8 clauses.

In response to:

In a minimal k-cnf formula, there should be 2k different k literals clauses exactly, so in a minimal 3CNF formula, there should be 23=8 different 3 literals clauses exactly.

So my question is now, what is the largest possible minimal 3CNF formula or how many clauses there are in the largest possible minimal 3CNF formula, i.e. what is the maximum number of clauses in the largest minimal 3CNF formula as function of n, where n is the number of variables in the 3CNF formula.

Is it $O(n)$? Is it $O(log(n))$? Is it $O(1)$, but just larger than 8?

1
source | link

What is the largest possible minimal 3CNF formula as function of the number of variables?

I have already defined here what is minimal 3CNF formula.

In the answer to the question, D.W. answered:

What you are thinking is wrong. A minimal, unsatisfiable formula can have more than 8 clauses.

In response to:

In a minimal k-cnf formula, there should be 2k different k literals clauses exactly, so in a minimal 3CNF formula, there should be 23=8 different 3 literals clauses exactly.

So my question is now, what is the largest possible minimal 3CNF formula or how many clauses there are in the largest possible minimal 3CNF formula, i.e. what is the maximum number of clauses in the largest minimal 3CNF formula as function of n, where n is the number of variables in the 3CNF formula.

Is it O(n)? Is it O(log(n))? Is it O(1), but just larger than 8?