Interesting. I'm actually not sure. The general result by Paris I cited is a little unclear. He proves CONSISTENCY (consistency of a set of personal probability statements) to be NP-complete. First he gets SAT \leq_P CONSISTENCY, but SAT is only O(2^n) in the number of atoms, not in the number of constraints. However, the corresponding positive result, that CONSISTENCY is in NP, is proven using an algorithm whose running time depends on the whole length of the input.
It could be that if you have the whole table in front of you, checking consistency is just checking that all the rows and columns sum to 1.
However, I don't think that looking at the complete joint distribution is the right formalization of the problem. For example, I have beliefs about 100 propositions, but it doesn't seem like I have 2^100 beliefs about the probabilities that they co-occur.
It's NP-hard. Here's a reduction from the complement problem of 3SAT: let's say you have n clauses of the form (p and not-q and r), i.e., conjunctions of 3 positive or negated atoms. Offer bets on each clause that cost 1 and pay n+1. The whole book is Dutch iff the disjunction of all the clauses is a propositional tautology.
I've written some speculations about what this might mean. The tentative title is "Against the possibility of a formal account of rationality":
http://cs.stanford.edu/people/slingamn/philosophy/against_rationality/against_rationality.pdf
I really like the Less Wrong community's exposition of Bayesianism so I'd be delighted to have feedback!
Oh, thanks, you're completely right.
To unify all the language and make things explicit: if you have n atoms, then there are 2^n possible states of the world (truth assignments to the atoms). Then, if you have a personal probability for each of the 2^n states ("complete joint distribution", "complete table"), you can check consistency by summing them and seeing that you get 1. This is O(n) in the size of the table.
The question at stake seems to be something like this: does the agent legitimately have access to her (exponentially large) complete joint distribution? Or does she only have access to personal probabilities for a small number of statements (for example, a few conjunctions of atoms)? In the second case, there may be no complete joint distribution corresponding to her personal probabilities (if she's inconsistent), exactly one (if the joint distribution is completely specified, possibly implicitly via independence assumptions that uniquely determine it), or infinitely many.