In this work we study knot theories with a parity property for crossings: every crossing is declared to be even or odd according to a certain preassigned rule. If this rule satisfies a set of simple axioms related to the Reidemeister moves, then certain simple invariants solving the minimality problem can be defined, and invariant maps on the set of knots can be constructed. The most important example of a knot theory with parity is the theory of virtual knots. Using the parity property arising from Gauss diagrams we show that even a gross simplification of the theory of virtual knots, namely, the theory of free knots, admits simple and highly nontrivial invariants. This gives a solution to a problem of Turaev, who conjectured that all free knots are trivial. In this work we show that free knots are generally not invertible, and provide invariants which detect the invertibility of free knots. The passage to ordinary virtual knots allows us to strengthen known invariants (such as the Kauffman bracket) using parity considerations. We also discuss other examples of knot theories with parity. © 2010 RAS(DoM) and LMS.