Without perfect information and transparency there's no way make lies illegal.

And who determines what's true and what's not?

At the risk of excessive red tape, the judicial system has been doing a reasonable job of determining facts in most modern countries.

It actually doesn't. Example: Did OJ kill anybody?

Judicial system engages in determining whether someone is guilty based on the evidence that it itself filters.

What about more complex things? Like what if I say "P = NP"? Is that a lie?

And then, do you want a trial for every comment? That will not work even for a fraction of comments.

>Like what if I say "P = NP"? Is that a lie?

That can't be determined to be a lie unless someone solves the problem. It's only a conjecture or assertion until then.

>And then, do you want a trial for every comment? That will not work even for a fraction of comments.

Only really has to apply to political statements made by the most powerful office holders, and only when contested, and only when there is a imminent intent to deceive and impact policy.

It's not really an all-or-nothing situation. It's just a matter of how much can be achieved within a reasonable cost.