How hard is Optical Character Recognition (OCR), formally? Let's assume an error tolerance comparable to a human (which is, I believe, around 98%).
In other words, where would it fit in the P/NP scale of problem complexity and intractability?
Or would it fit on that scale? Just what kind of problem is it?
I'm not terribly familiar with the formal definition of problem complexity. I'm just curious.
Well in order to rate a problem in a computability scale you need to know what kind of computation model you are using. The problem as defined is not computable by any machine.
So I guess your question resembles asking how hard it is for a person to do complex calculations.
You can think of it this way, the human brain is by definition non deterministic moreover you can't exactly rate it as a computing model since it's not exactly measurable how many actions a human does when thinking of a problem. It's not discrete procedure.