We study the computational complexity of fundamental problems over the p-adic numbers ℚp and the p-adic integers ℤp. Guépin, Haase, and Worrell [9] proved that checking satisfiability of systems of linear equations combined with valuation constraints of the form vp(x) = c for p ≥ 5 is NP-complete (both over ℤp and over ℚp), and left the cases p = 2 and p = 3 open. We solve their problem by showing that the problem is NP-complete for ℤ3 and for ℚ3, but that it is in P for ℤ2 and for ℚ2. We also present different polynomial-time algorithms for solvability of systems of linear equations in ℚp with either constraints of the form vp(x) ≤ c or of the form vp(x) ≥ c for c ∈ ℤ. Finally, we show how our algorithms can be used to decide in polynomial time the satisfiability of systems of (strict and non-strict) linear inequalities over ℚ together with valuation constraints vp(x) ≥ c for several different prime numbers p simultaneously.