It doesn't depend at all - all the legislation and regulations are online..
Precisely. The relevant regulation in this case being available here:
udsc.gov.pl/Wykonywanie,pracy,przez,cudzoziemcow,w,RP,511.html
"Ponadto na podstawie rozporządzenie Ministra Pracy i Polityki Społecznej z dnia 30 sierpnia 2006 r. w sprawie wykonywania pracy przez cudzoziemców bez konieczności uzyskania zezwolenia na pracę (Dz. U. Nr 156, poz. 1116, z 2007 r. Nr 120, poz. 824, z 2008 r. Nr 17, poz. 106, z 2009 r. Nr 21, poz. 114) wykonywanie pracy przez cudzoziemców na terytorium Rzeczypospolitej Polskiej bez konieczności uzyskania zezwolenia na pracę jest dopuszczalne w przypadku cudzoziemców:" (Rough translation: "Annex to the base regulation of the Employment Secretary and the social policy from 30 August 2006 r. the performance of work by foreigners without the need to obtain a work permit (Dz. At. No. 156, pos. 1116, from 2007 r. No. 120, pos. 824, from 2008 r. No. 17, pos. 106, from 2009 r. No. 21, pos. 114) the performance of work by foreigners in the Republic of Poland without the need to obtain a work permit is acceptable in case of foreigners:")
"3) będących nauczycielami języków obcych lub prowadzących zajęcia w językach obcych, którzy wykonują pracę w ramach umów i porozumień międzynarodowych, których Rzeczpospolita Polska jest stroną;
4) będących nauczycielami języków obcych, którzy wykonują pracę w przedszkolach, szkołach lub placówkach, o których mowa w przepisach o systemie oświaty, lub Ochotniczych Hufcach Pracy;
5) będących nauczycielami języków obcych, którzy wykonują pracę w zakładach kształcenia nauczycieli, o których mowa w przepisach o systemie oświaty;" (Rough translation: "3)being teachers of foreign languages or giving classes in foreign languages which perform the work as part of international treaties and agreements, of which Republic Poland is a side; 4) being teachers of foreign languages which perform the work at nursery schools, or institutions which are being specified in regulations of the educational system, or Voluntary scout troops of the Work; 5) being teachers of foreign languages which perform the work at units of the teacher education which are being specified in regulations of the educational system;").
Then you look at menis.pl/prawo_oswiatowe.htm to see which institutions are specified. Here's a hint: just calling a business venture "The OK Super-Cool School" does not make it an acceptable institution.